[자료구조] 이진 탐색(Binary Search)

이진 탐색이란?

- 테이터가 정렬되어있는 배열에서 특정 값을 찾을때 중간에 있는 임의의 값을 선택하여 특정값X와 비교한다.

X가 중간값보다 작으면 중간값을 기준으로 좌측의 데이터들을 대상으로, 중간값보다 크면 우측의 데이터들을 대상으로 동일한 방법으로 다시 중간값을 임의로 선택해서 비교하는 과정을 X값을 찾을때까지 반복한다.

- 이진탐색에 사용되는 배열은 정렬이 되어있어야 한다.

- 구역을 나누었을때 first(첫번째 인덱스)가 last(마지막 인덱스)보다 커지면 해당 배열에 특정값이 없다고 판단하여 탈출하는 부분을 구현해야한다.

- 시간 복잡도 : O(logn)

 

int BSearchRecursive(int arr[], int target, int low, int high) {
    if (low > high)
        return -1;

    int mid = (low + high) / 2;
    if (arr[mid] == target)
        return mid;
    else if (arr[mid] > target)
        return BSearchRecursive(arr, target, low, mid-1);
    else
        return BSearchRecursive(arr, target, mid+1, high);
}