Binary search (이진 탐색)

1. Binary search 란 ?

 

Binary Search 란 정렬 된 배열에서 특정 값을 찾기 위해 사용되는 Search 알고리즘입니다.

O(logN) 의 시간복잡도로, 빠른 시간 내에 원하는 값을 찾을 수 있습니다.

 

2. Binary Search 의 방법 

 

위키피디아 참조

1) 배열의 가장 왼쪽(left) index와 가장 오른쪽(right) index의 중간값(center = (left+right)/2)을 선택하여 찾고자 하는 값과 비교합니다.

2) 원하는 값이 center 보다 작다면, center 기준 왼쪽 배열을 선택하여 1의 과정을 반복합니다. ( right = center )

3) 원하는 값이 center 보다 크다면, center 기준 오른쪽 배열을 선택하여 1의 과정을 반복합니다. ( left = center )

4) 만약 center의 값이 원하는 값과 일치한다면 값을 찾은것입니다.

 

3. Code

// This is binary search algorithm

#include <iostream>

using namespace std;

int search(int arr[], int left, int right, int x);

int main() {
    // Sorted array
    int a[17] = {1, 3, 4, 6, 7, 8, 10, 13, 14, 18, 19, 21, 24, 37, 40, 45, 71};
    int len = sizeof(a) / sizeof(*a);
    cout << "size of array: " << len << endl;

    // we will find "2"'s index in the array a
    int idx = search(a, 0, len-1, 7);
    if ( idx == -1 ) {
        cout << "Failed to find x" << endl;
    } else {
        cout << "Found x in idx " << idx << endl;
    }

    return 0;
}

int search(int arr[], int left, int right, int x) {
    
    while( left <= right ) {
        int center = (left + right) / 2;
        if ( arr[center] == x) {
            cout << "Found value " << x << endl;
            return center;
        } else if( arr[center] < x ) {
            cout << "value idx is in right side of center" << endl;
            left = center;
        } else {
            cout << "value idx is in left side of center" << endl;
            right = center;
        }
    } 

    cout << "Failed to find value x" << endl;
    return -1;
}