이분 탐색 (Binary Search)

• 이분 탐색(Binary Search)

이분 탐색은 정렬된 배열에서 값을 찾는 효율적인 알고리즘이다.

 

어릴 적 친구와 1부터 100까지의 수 중 숫자 맞추기를 할 때 똑똑한 친구들은 50보다 커?(ㅇㅇ) 75보다 커?(ㄴㄴ) 이런 식으로 반 씩 줄여서 질문을 했을 것이다. 이것이 이분 탐색이다.

 

이 알고리즘은 배열을 차례대로 탐색하는 것이 아니라, 중간 값을 기준으로 탐색 범위를 계속해서 반으로 줄여나간다.

 

이로 인해 시간복잡도가 O(log n)으로 효율적이다.

 

아래 표에서 2를 찾아보겠다.

1

2

3

4

5

6

7

8

9

 

먼저 중간 값인 5를 탐색한다. 2는 5보다 작기에 5보다 큰 값들은 신경 쓰지 않는다.

1

2

3

4

5

 

남은 값들 중 중간 값인 3을 탐색한다. 2는 3보다 작기에 3보다 큰 값들은 신경 쓰지 않는다.

1

2

3

 

남은 값들 중 중간 값인 2를 탐색한다. 우리가 찾던 값임으로 알고리즘은 종료된다.

2

 

 

---

• C언어로 구현한 이진탐색

#include <stdio.h>

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

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

        // 목표 값을 찾았을 때
        if (arr[mid] == target) {
            return mid;
        }

        // 목표 값이 중간 값보다 클 경우 오른쪽 부분 탐색
        if (arr[mid] < target) {
            left = mid + 1;
        }
        // 목표 값이 중간 값보다 작을 경우 왼쪽 부분 탐색
        else {
            right = mid - 1;
        }
    }

    // 값을 찾지 못했을 때
    return -1;
}

int main() {
    int arr[] = {2, 3, 4, 10, 40};
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 10;
    int result = binarySearch(arr, size, target);

    if (result != -1) {
        printf("Element is present at index %d\n", result);
    } else {
        printf("Element is not present in array\n");
    }

    return 0;
}