이진탐색 사용처

가장 간단한 탐색 알고리즘은 선형 탐색 Sequential Search으로써 n개의 자료를 순서대로 하나씩 탐색하는 방법이다.

 

자료가 정렬된 상태에서는 이진탐색 Binary Search이 효율적이다. 

이진탐색은 전체 자료의 중간에 있는 자료와 키값을 비교한다.

만약 일치하지 않는다면 찾고자 하는 자료는 앞부분 또는 뒷부분 중 어느 한 곳에 있다.

(한번 탐색 후 다시 탐색할 자료 개수가 약 1/2로 줄어든다.)

예를 들어 1000개의 자료를 탐색한다면 2^10=1024이므로 최대 10번만 탐색하면 된다.

비교 결과, 키값이 가운데 있으면 인덱스 n을 반환,

왼쪽에 있으면 0~n-1, 오른쪽에 있으면 n+1~끝,

없으면 flag -1을 반환하게 한다.