이진 탐색 알고리즘

중간 값을 임의의 값으로 선택하여, 그 값을 찾고자 하는 값과 크고 작음을 비교하는 방식을 채택

방식

처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최고값이 되며, 작으면 그 값은 새로운 최하값이 된다.

검색이 반복될 때마다 목표값을 찾을 확률은 두배가 된다. 이진 검색은 분할정복 알고리즘의 한 예이다.

탐색 시간

O(logn)