Binary Search/이진 검색

이진 검색은 데이터가 정렬되어있을 경우에 사용가능 한 검색 알고리즘이다.

선형검색보다 더 빠르다는 장점이 있다.

이진 검색은 인덱스의 중간에서 시작하고 중간 인덱스의 원소가 키 값보다 크면 첫번째 인덱스 부터 중간 인덱스 - 1

까지 검색해주고, 키 값보다 작으면 중간 인덱스부터 마지막 인덱스까지 검색을 해주고 이를 반복한다.

예를 들어 배열 안의 원소가 [ 1, 2, 3 ,4 ,5 ,6 ,7, 8]이 있을때  6을 찾으려고 하면 
(0 + 7) / 2 =  3은 중간 값인데 찾는 키값은 6이다 따라서 중간 값보다 1 더 큰 4번 인덱스를  시작 인덱스 값으로 넣어주고 다시 검색을 하면 (4 + 7) / 2 = 5이다 아직도 찾는 값이 아니다 그리고 다음 중간 값은  (5 + 7) / 2 = 6 키 값을

찾았으면 키값과 일치하는 인덱스를 리턴한다.

 

코드

#include <iostream>
using namespace std;

int Binary_Search(const int arr[], int size, int key){
    int pl = 0, pr = size - 1, pc;
    do{
        pc = (pl + pr) / 2;
        if(arr[pc] == key){
            return pc;
        }
        else if(arr[pc] < key){
            pl = pc + 1;
        }
        else{
            pr = pc - 1;
        }
    }while(pl <= pr);
    return -1;
}

int main(){
    int arr[] = { 1,2,3,4,5,6,7,8,9,10 }; // 10
    cout << "Run start." << endl;
    if(int key = Binary_Search(arr, 10, 10) > -1 ? Binary_Search(arr, 10, 10) : 0){
        cout << "Binary Search success key index is = " << key << endl;
    }
    else{
        cout << "Do not found key index" << endl;
    }
    if(int key = Binary_Search(arr,10,999) > -1 ? Binary_Search(arr, 10, 999) : 0){
        cout << "Binary Search success key index is = " << key << endl;
    }
    else{
        cout << "Do not found key index" << endl;
    }
    return 0;
}

시간 복잡도는 O(log n)이다.

이진 검색을 응용한 최적해를 구하는 알고리즘 Parametric Search라는 기법도 있는데 이는 다음에 알아보도록 하자.