4. BinarySearch( 이진 탐색 )

이진 탐색에서 반드시 배열은 정렬되어 있어야 한다. 

아래는 이진탐색의 수도 코드이다.

위의 의사코드를 보면 list는 탐색할 배열, low는 탐색 시작 인덱스, high는 탐색 마지막 인덱스이다.

list[low]에서 list [high]에서의 탐색은 list[low]에서 list[middle-1]의 탐색이 되거나

list[middle+1]에서 list[high]에서의 탐색이 된다.

이들 2가지의 탐색은 원래 문제의 크기를 반으로 줄인 부분 문제가 되고,

따라서 재귀 호출을 이용하여 쉽게 만들 수 있다.

​맨 처음에 BinarySearch함수의 탐색 범위는 low가 0, high가 n-1이 되어 배열 전체가 탐색 범위가 된다.

재귀 함수의 탈출조건은 low가 high보다 커지는 경우로 이 경우는 탐색 실패가 된다.

 

아래는 위의 수도 코드를 바탕으로 만든 이진 탐색 함수.

아래는 메인 함수

 

아래는 프로그램 결과값