이진 탐색(Binary Search)

✔️ 이진 탐색이란?

이진 탐색이란 데이터가 정렬되어 있는 배열에서 특정한 값을 찾아내는 알고리즘입니다.

배열의 중간에 있는 임의의 값을 선택하여 찾고자 하는 값 X와 비교합니다.

만약 X가 중간 값보다 작으면 중간 값을 기준으로 좌측의 데이터들로, X가 중간 값보다 크면 중간 값을 기준으로 우측의 데이터들로

다시 탐색을 시작하여 해당 값을 찾을 때까지 반복합니다.

 

📌 시간 복잡도

N개의 배열을 이진 탐색하게 되면 N, N/2, N/4, N/8 ... 으로 진행될 것입니다.

여기서 탐색 횟수가 시간 복잡도가 될 것이고 그 값을 K라고 한다면 K = log2N일 것입니다.

즉, 이진 탐색의 시간 복잡도는 O(logN)입니다. 

 

✔️ 이진 탐색의 예시

1. 예를 들어 { 17, 28, 43, 67, 88, 92, 100 } 의 오름차순으로 정렬된 배열에서 43의 값을 찾는 과정입니다.

 

2. 첫 번째 시도로 가운데의 임의의 값 67을 선택하고 67과 43을 비교합니다.

 

3. 43 < 67 이므로 43은 가운데 값 67의 좌측에 있다는걸 알 수 있습니다.

 

4. 두 번째 시도로 67의 좌측 값을인 { 17, 28, 43 } 을 기준으로 다시 탐색합니다.

 

5. 좌측 배열 들의 가운데 임의의 값인 28을 기준으로 하면 28 < 43 이므로 28의 우측에 있다는걸 알 수 있습니다.

 

6. 28의 우측 값으로 배열을 다시 설정하면 { 43 } 이 남고 우리가 원하는 값인 43을 찾을 수 있게 됩니다.

 

✔️ 예시 코드

int binary_search(int arr[], int left, int right, int key) {
    int mid = (left + right) / 2;

    if(arr[mid] == key) {
        return mid;
    }
    else if(arr[mid] > key) {
        return binary_search(arr, left, mid - 1, key);
    }
    else {
        return binary_search(arr, mid + 1, right, key);
    }
}

이 때 arr는 오름차순으로 정렬된 배열, left는 배열의 첫 번째 인덱스, right는 배열의 마지막 인덱스, key는 우리가 원하는 값입니다.

mid값을 구한 후 우리가 원하는 값과 비교하여 재귀함수를 통해 배열을 재설정하는 방식으로 구현하였습니다.

우리가 원하는 값을 찾을 시 정렬된 배열에서 해당 값의 인덱스를 반환합니다.

 

📄 참고

https://cjh5414.github.io/binary-search/