[Algorithm] 이분 탐색

이분 탐색 (Binary Search)

• 탐색 범위를 두 부분으로 분할하면서 찾는 방식

• 처음부터 끝까지 돌면서 탐색하는 것보다 훨씬 빠른 장점을 지닌다.

시간복잡도

• 전체 탐색 : O(N)
• 이분 탐색 : O(logN)

• 단점이라면 항상 배열을 정렬하고서 찾아야 한다는 점?

⭕️ 정렬된 자료 구조에서 특정 값을 찾기 위해 범위를 절반씩 나눠가며 찾는다.

이해가 어렵다면 UP/DOWN 게임을 생각하자.
나는 65를 생각했다. 상대가 맞추기 위해 숫자를 말할거고 나는 up,down만 이야기 한다.
범위를 줄이는 가장 효과적인 방법은 해당 범위를 반으로 쪼개서 생각하는 것!
0~100이기에 50을 부르면 UP -> 50~100이기에 75를 부르면 down ->
50~75이기에 63을 부르면 up -> 63~75 사이를 부르면서 찾게 된다!!

진행 순서

• 정렬을 해야 한다.
• left, right로 mid값을 설정한다.
• mid와 내가 구하고자 하는 값을 비교한다.
• 구할 값이 mid보다 높으면 : left = mid+1
• 구할 값이 mid보다 낮으면 : right = mid-1
• left > right가 될 때까지 계속 반복하기.

Code

특정 배열에서 특정 수를 찾는데에 있어서 재귀 함수를 이용한 코드가 있다.

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);
}