오늘은 이진 정렬에 대하여 알아보겠습니다.

개요

자료의 가운데에 있는 항목을 키값과 비교하여 키값이 더 크면 오른쪽 부분을 검색하고, 키값이 더 작으면 왼쪽 부분을 검색하는 방법을 이진 탐색이라고 합니다.

가운데에 있는 값을 기준으로 왼쪽과 오른쪽으로 나누어 검색하므로 이분 탐색이라고도 합니다.

키를 찾을 때까지 이진 탐색을 재귀적으로 반복하며 검색 범위를 절반으로 줄여가므로 더 빠르게 검색하게 됩니다.

이진 탐색은 자료가 정렬되어 있는 산태에서만 사용할 수 있습니다.

알고리즘

binary(arr[],l,h,k){
    middle <- (l+h)/2;
    if(k = arr[middle]) then{
        return i;
    }
    else if(k<arr[middle])then{
        binary(arr[],l,middle-1,k);
    }
    else if(k>arr[middle])then{
        binary(arr[],middle+1,h,k);
    }
    else{
        return -1;
    }
}

다른 검색방법에 비하여 성능은 좋지만, 삽입이나 삭제를 수행해도 항상 정렬상태로 두어야 되기 때문에 별도의 작업이 필요합니다.