이진 탐색(Binary Search)

이진 탐색 = 이분 탐색 (Binary Search) 정렬된 배열 또는 리스트에 적합한 고속 탐색 방법이다. 배열의 중앙에 있는 값을 조사하여 찾고자 하는 항목이 왼쪽 또는 오른쪽 부분 배열에 있는지를 알아내어 탐색의 범위를 반으로 줄인다.

찾고자 하는 값이 속해있지 않은 부분은 전혀 고려할 필요가 없기 때문에, 매 단계에서 검색해야 할 리스트의 크기를 반으로 줄일 수 있다. 이러한 방법을 반복적으로 사용해 탐색하는 방법이 이진 탐색이다.

데이터의 삽입이나 삭제가 빈번할 시에는 적합하지 않고, 주로 고정된 데이터에 대한 탐색에 적합하다. 이진 탐색의 구현 1.

탐색의 대상이 되는 자료들이 array[low] 에서부터 array[high]에 들어있다고 가정하자. (정렬되어 있어야 함) 즉 어떤 시점에서 탐색되어야 할 범위는 low에서 high 까지가 된다.

맨 처음 low에는 0번 인덱스의 값, high에는 n-1번 인덱스의 값이 들어갈 것이다. 2. low와 high값에 의거해 중간...