이진 탐색
-
4. BinarySearch( 이진 탐색 )C 자료구조/1. 재귀함수 2020. 6. 8. 19:15
이진 탐색에서 반드시 배열은 정렬되어 있어야 한다. 아래는 이진탐색의 수도 코드이다. 위의 의사코드를 보면 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보다 커지는 경우로 이 경우는 탐색 실..