[자료구조 & 알고리즘] 이분 탐색 (Binary Search)

 

이분 탐색 (Binary Search) 알고리즘

이분 탐색(Binary Search)은 정렬된 배열에서 특정 값을 빠르게 찾는 알고리즘입니다. 탐색 범위를 절반으로 줄이기 때문에 시간 복잡도가 O(log⁡N)O(\log N)으로 매우 빠릅니다. 이번 포스트에서는 이분 탐색의 개념, 동작 방식, 그리고 C 언어로 구현한 예제를 자세히 설명합니다.

---

1. 이분 탐색이란?

이분 탐색은 데이터를 절반씩 나누며 탐색 범위를 좁혀가는 방식으로 동작합니다. 이 과정은 반복적으로 수행되어 결국 원하는 값에 도달하게 됩니다.
단, 데이터가 반드시 정렬되어 있어야 한다는 전제 조건이 있습니다.

---

2. 이분 탐색의 동작 과정

1. 배열의 중간 값을 선택합니다.
2. 중간 값이 찾고자 하는 값과 같으면 탐색을 종료합니다.
3. 중간 값이 찾고자 하는 값보다 크면 왼쪽 절반만 탐색합니다.
4. 중간 값이 찾고자 하는 값보다 작으면 오른쪽 절반만 탐색합니다.
5. 이 과정을 반복하여 값이 발견되거나 탐색 범위가 없어질 때까지 진행합니다.

---

3. 이분 탐색의 C 코드 구현

아래는 이분 탐색을 반복문을 사용하여 구현한 C 코드입니다.

#include <stdio.h>

int binary_search(int arr[], int size, int target) {
    int left = 0, right = size - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;  // 중간 인덱스 계산

        if (arr[mid] == target) {
            return mid;  // 값이 발견되면 해당 인덱스를 반환
        } else if (arr[mid] < target) {
            left = mid + 1;  // 오른쪽 절반 탐색
        } else {
            right = mid - 1;  // 왼쪽 절반 탐색
        }
    }

    return -1;  // 값을 찾지 못한 경우
}

int main() {
    int arr[] = {1, 3, 5, 7, 9, 11, 13};
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 7;

    int result = binary_search(arr, size, target);

    if (result != -1) {
        printf("값 %d는 배열의 %d번째 인덱스에 있습니다.\n", target, result);
    } else {
        printf("값 %d를 배열에서 찾을 수 없습니다.\n", target);
    }

    return 0;
}

---

4. 코드 설명

4-1. 중간 인덱스 계산

int mid = left + (right - left) / 2;

• left + right 대신 left + (right - left) / 2를 사용하여 **오버플로우(Overflow)**를 방지합니다.
• 예를 들어, left = 2147483640, right = 2147483647일 때 left + right가 int 범위를 초과하여 오류가 발생할 수 있습니다.
  이를 방지하기 위해 (right - left)를 먼저 계산하는 방식으로 안전하게 중간 값을 구합니다.

---

4-2. 조건 분기

1. 값이 일치하는 경우
   • 배열의 중간 값이 찾고자 하는 값과 같으면 해당 중간 인덱스를 반환합니다.
2. if (arr[mid] == target) { return mid; }
3. 오른쪽 절반 탐색
   • 중간 값이 목표 값보다 작을 경우, 왼쪽 절반을 제외하고 탐색 범위를 오른쪽으로 좁힙니다.
4. else if (arr[mid] < target) { left = mid + 1; }
5. 왼쪽 절반 탐색
   • 중간 값이 목표 값보다 클 경우, 오른쪽 절반을 제외하고 탐색 범위를 왼쪽으로 좁힙니다.
6. else { right = mid - 1; }

---

4-3. 반복문 종료 조건

• left가 right보다 커지는 경우 탐색이 종료됩니다.
• 탐색이 종료되었을 때 값이 발견되지 않으면 -1을 반환하여 값을 찾지 못했음을 나타냅니다.

---

5. 실행 예시

5-1. 입력 값

• 배열: {1, 3, 5, 7, 9, 11, 13}
• 목표 값: 7

5-2. 출력 결과

값 7는 배열의 3번째 인덱스에 있습니다.

---

6. 시간 복잡도 분석

• 최선의 경우: O(1)O(1) – 중간 값이 처음부터 목표 값과 일치할 때
• 평균 및 최악의 경우: O(log⁡N)O(\log N) – 탐색 범위를 절반씩 줄여가며 진행할 때 발생

---

7. 이분 탐색의 장점과 단점

7-1. 장점

• 정렬된 데이터에서 매우 빠른 탐색이 가능
• 큰 데이터에서도 효율적으로 동작 (O(log⁡N)O(\log N) 복잡도)

7-2. 단점

• 데이터가 정렬되어 있어야 한다는 전제 조건이 필요
• 정렬되지 않은 데이터를 탐색할 경우 사전 정렬 시간이 추가로 소요됨

---

 

💡 도움이 되셨다면 댓글과 공감 부탁드립니다! 😊
📌 더 많은 알고리즘 풀이와 프로그래밍 자료는 블로그에서 확인하세요!
✉️ 문의나 피드백은 댓글이나 이메일로 남겨주세요.