이분 탐색(Binary Search)

이분 탐색

"1 3 5 7 9 11 13 15 17 19에서 13는 몇 번째 위치에 존재하는가?"
이 문제에서 숫자들은 정렬되어 있는 상태이다. 이때 배열을 반씩 나누어 탐색을 하게 되면 첫 번째 숫자부터 탐색하는 것보다 빠르게 탐색할 수 있게 된다. 이러한 방법을 이분 탐색이라 한다.

수행 과정

배열은 총 10개의 숫자로 이루어져있다.
1. 이를 반으로 나눌 기준이 되는 숫자는 11이 된다. 11은 13보다 작은 숫자이기 때문에 11보다 작은 숫자들은 배열에서 제외한다.
2. 남은 숫자들 중 반으로 나누는 기준은 15가 된다. 15는 13보다 큰 숫자이기 때문에 15보다 큰 숫자들은 배열에서 제외한다.
3. 마지막으로 남은 숫자가 13이 되면서 탐색은 종료된다.

시간 복잡도

위 과정을 수행했을 때 시간 복잡도는 O(log2N)이 된다.

코드 구현

이분 탐색을 구현하면 다음과 같다.

#include <iostream>

using namespace std;

int arr[10] = {1,3,5,7,9,11,13,15,17,19};
int target = 13;

int binary_search(int start, int end) {
    if (start > end) return -1;
    
    int mid = (start + end) / 2;
    if (arr[mid] > target) return binary_search(start, mid - 1);
    else if (arr[mid] < target) return binary_search(mid + 1, end);
    else return mid;
}

int main() {

    int idx = binary_search(0, sizeof(arr)/sizeof(int) - 1);
    cout << idx;

    return 0;
}
//6

Reference

https://m.blog.naver.com/PostView.naver?blogId=ndb796&logNo=221275413971&navType=by