1. Introduction 이진탐색은 정렬된 리스트에 적용할 수 있는 간단한 고속 탐색 기법이다. 해시 같은 매핑 기반의 기법을 제외한다면 가장 빠른 탐색 속도를 보장한다. 2. Method 이진탐색의 핵심은 전체 탐색범위를 반으로 나눠서 찾고자 하는 원소 (이하 target, $T$)가 없을 것으로 기대되는 쪽을 버리는 것이다. 이를 통해 탐색범위는 기존의 탐색범위의 $1\over2$이 되고, 이 새로운 탐색 범위에 반을 버려가는 과정을 반복하여 결과적으로 target을 찾아내는 방법이다. 과정을 자세하게 알아보자. 탐색을 원하는 구간 [a, b]에 대해 a를 low, b를 high라고 하자. (당연히 low, high는 index이다) low와 high의 중간 값을 mid라고 하자. 탐색할 리스트를..