6.3 이진 탐색(Binary Search)

이진 탐색(Binary Search) 알고리즘은 정렬 상태의 배열에서 원하는 자료를 탐색하는 알고리즘으로 재귀적인 방법으로 구현할 수 있는 대표적인 알고리즘입니다.

배열의 중간에 있는 요소와 검색 자료를 비교하여 크면 뒤쪽 배열에서 재귀적으로 탐색하고 작으면 앞쪽 배열에서 재귀적으로 탐색합니다. 만약 같은 자료를 찾거나 배열의 원소 개수가 0이면 탐색을 끝냅니다.이진 탐색 알고리즘

위치 BinarySearch(base: 배열, n: 원소 개수, value: 검색할 값)

    조건 n<=0

        0 반환

    gap = base[n/2] – value;

    if(gap == 0)

        반환 base + n/2

    if(gap>0)

        반환 BinarySearch(base,n/2, fun)

    반환 BinarySearch(base+n/2+1,n – n/2, fun) 

순차 탐색한다면 최악의 경우 모든 요소와 비교해야 하므로 O(n) 성능을 보입니다. 하지만 이진 탐색에서는 n/(2의 0승), n/(2의 1승), n/(2의 2승),…,n/(2의 h승)개일 때 가운데 요소와 1번씩만 수행합니다. n/(2의 h승)이 1이면 더이상 비교하지 않으므로 O(logn) 성능을 보입니다.

“순차 탐색 속도 O(n), 이진 탐색 속도 O(logn)”