[알고리즘] 이진검색

14 Jan 2021

선형검색이 인덱스를 처음부터 원하는 값을 찾을 때 까지 하나하나 살펴보는 방법이라면,
이진검색은 배열에서 찾고자 하는 값을 찾을 때까지, 즉 후보 범위를 하나로 좁힐 때 까지, 찾고자 하는 값을 포함하는 리스트를 반으로 나누는 과정을 반복한다.

배열에서 어떤 항목(값)을 찾을 때,
추측값의 현 범위를 계속 파악하는 것

그림으로 표현한다면 다음과 같다.

이진검색 과정을 글로 써본다면 다음과 같다.

배열의 크기를 알아낸다.
찾고자 하는 값이 포함된 리스트 범위를 나타내는 min과 max 변수를 선언한다. 처음 min에는 배열의 첫 인덱스인 0, max에는 마지막 인덱스인 size-1
추측값은 min과 max의 평균이다.
if 추측값 == 정답 : break
else if 추측값 > 정답 : max = 추측값-1
else (추측값 < 정답) : min = 추측값+1

코드로 작성하면 다음과 같다.

#include <iostream>
using namespace std;

int binarySearch(int answer, int *arr, int size){

    cout << "size : " << size << endl;
    int min = 0; int max = size-1;
    int avg;

    while(1){
        avg = (max+min)/2;
        cout << "avg : " << avg << endl;
        if(arr[avg] == answer){
            cout<< "found!" << endl;
            break;
        }
        else if(arr[avg] > answer){
            max = avg-1;
            cout << "max : " << max << endl;
        } else {
            min = avg+1;
            cout << "min : " << min << endl;
        }
    }
    return arr[avg];
}

int main(){
    int answer;
    cin >> answer;
    int arr[25] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97};

    cout << binarySearch(answer, arr, 25) << endl;
}