이진 검색(Binary Search) 알고리즘

이진 검색(Binary Search) 알고리즘이란?

이미 키 값으로 정렬된 데이터를 대상으로, 중앙 값을 이용해 검색하는 알고리즘.

전체 데이터의 중앙 값을 찾아 검색하려는 데이터와 비교하여

중앙 값보다 작으면 왼쪽 부분의 중앙 값을 다시 취하고, 중앙 값보다 크면 오른쪽 부분의 중앙 값을 다시 취해 비교하는 작업을 반복하는 알고리즘.

선형 검색보다 좀 더 빠르다.

 

자바로 구현하기

//요솟수가 n인 배열 a에서 key와 같은 요소를 이진 검색한다.
static int binSearch(int[] a, int n, int key) {
    int pl = 0;
    int pr = n-1;

    while(pl<=pr){
        int pc = (pr+pl)/2;
        if(key == a[pc]) {
            return pc;
        } else if (key > a[pc]) {
            pl = pc+1;
        } else if (key < a[pc]) {
            pr = pc-1;
        }
    }
    return -1;
}