이진탐색(이분검색)

이진탐색은 탐색할 대상 배열이 정렬되어있을 때만 사용할 수 있는 탐색법이다.

배열의 중앙에 있는 값을 이용하여 찾고자 하는 항목이 기준값의 왼쪽 있는지 오른쪽에 있는지를 알아내어

탐색범위를 반으로 줄일 수 있다. 값이 속해있지 않은 부분은 고려하지 않아도 되기 때문에,

매 단계에서 탐색 범위를 반으로 줄여 나갈 수 있다.

데이터의 삽입이나 삭제가 빈번한 경우에는 적합하지 않고, 주로 고정된 데이터에 대한 탐색에 적합하다.

 

탐색되어야 할 범위의 인덱스[0]를 Low, 인덱스(n-1)를 High라고 할 때 중간값 Mid는 (low+high)/2이다.

구하고자 하는 값이 중간값보다 높다면 low를 mid+1로 만들어주고(탐색범위 오른쪽 반으로 줄어듬)

중간값보다 낮다면 high를 mid-1로 만들어 준다.(탐색범위 왼쪽 반으로 줄어듬)

이를 반복해  탐색하는 값이 Index [M]과 일치하면 탐색에 성공한다.