탐색(2): 이진 탐색

이진 탐색 (binary search)

데이터가 정렬되어 있는 상태에서 중앙값 비교를 통해 대상을 축소하면서 원하는 값을 탐색하는 알고리즘

 

* 탐색 과정 (오름차순의 경우):

(i) 대상 데이터의 중앙값을 선택하고, 찾고자 하는 값과 중앙값을 비교

(ii) 중앙값보다 작다면 왼쪽 데이터를 선택 or 중앙값보다 크면 오른쪽 데이터를 선택

(iii) 중앙값과 찾고자하는 값이 일치할 때까지 위의 두번째 과정을 반복