이진 탐색

정렬된 목록에서 원하는 값을 찾을 때, 가운데 값과 비교해서 찾는 범위를 절반씩 줄여나가는 방법이다. 가운데 값이 찾는 값보다 크면 앞쪽 절반만, 작으면 뒤쪽 절반만 다시 본다. 처음부터 끝까지 하나씩 보는 것(O(n))보다 훨씬 빠르게(O(log n)) 찾지만, 목록이 미리 정렬되어 있어야 한다.