1. Uniform binary search 이진탐색의 mid는 현재 값에서 항상 일정한 값 만큼만 차이나게 된다. 즉 현재 a[mid]의 값을 검사했다면 다음에 검사할 값은 a[mid + k] or a[mid - k] 이다. 따라서 매 루틴마다 다음 mid까지의 거리 k를 미리 look-up table에 저장해둔다. 이 결과를 통해 mid를 정하는 산술연산이 불필요하게 된다. 같은 배열에 대해 많은 쿼리를 처리해야하는 환경에서 빠르게 동작한다. 2. Exponential binary search 이 방법은 target의 범위를 고정하는 방법이다. 시작부터 bound의 범위를 2배로 늘려가며 target의 상한을 찾는다. 상한을 찾았으면 target의 범위는 [bound / 2, bound+1] 사이에 ..

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