이진탐색의 Variation

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] 사이에 있으므로 이 범위에서 이진탐색을 수행한다. 탐색 범위의 측면에서는 상한이 배열의 끝까지가도 bound / 2가 배열의 정중앙 뒤쪽에 있다면 결국 [bound / 2, size] 만큼만 탐색을 하기 때문에 bound / 2가 배열의 후반부에 있을 수록 유리하다. 하지만 경험적으로 target이 배열의 초반에 위치하지 않는 이상 큰 이득은 보지 못한다고 한다.

---

3. Interpolation binary search

이 방법은 mid를 단순하게 high와 low의 중간값이 아니라, target이 실제 high, low의 값에 비해 얼마나 떨어지있는지를 반영하는 방법이다. 배열이 1, 4, 7, 10, ... 이런식으로 uniformly distruted 할 때 쓰인다. 그렇지 않으면 적절한 mid값을 찾지 못한다. 시간복잡도는 $O(log(log\; n))$이다.

---

4. Implement

다음은 이진탐색의 구현이다. 파이썬으로 구현되어있으며, recursive, non-recursive, alternative, uniform, exponential, interpolation의 6가지 이진탐색 기법을 구현했다.

import random as rand
import time
import math

def Binary_Search_recursive(a, target, low, high):
    
    if low >= high:
        return -1
    
    mid = (low + high) // 2
    if a[mid] > target:
        return Binary_Search_recursive(a, target, low, mid - 1)
    elif a[mid] < target:
        return Binary_Search_recursive(a, target, mid+1, high)
    else:
        return mid
    
def Binary_Search_nonRecursive(a, target, low, high):
    
    while low <= high:
        mid = (low + high) // 2
        if a[mid] > target:
            high = mid - 1
        elif  a[mid] < target:
            low = mid + 1
        else:
            return mid
        
        return -1

def alternative_Binary_Search(a, target, low, high):
    while low < high:
        mid = (low + high) // 2
        if a[mid] > target:
            high = mid - 1
        else:
            low = mid + 1
    if a[low] == target:
        return low
    return -1

def uniform_Binary_Search(a, target):
    mid = lut[0] - 1
    i = 0
    
    while True:
        if target == a[mid]:
            return mid
        elif lut[i] == 0:
            return -1
        elif target < a[mid]:
            mid -= lut[i]
        else:
            mid += lut[i]
        i += 1
    

def build_lookupList(a):
    lookupList = []
    
    N = math.floor(math.log(len(a)))
    power = 1
    p = -1
    while p != 0:
        half = power
        power *= 2
        p = (N+half) // power
        lookupList.append(p)
    
    return lookupList

def Binary_Search_exponential(a, target, low, high):
    bound = 1
    while(bound < len(a) and a[bound] < target):
        bound *= 2
    
    return Binary_Search_nonRecursive(a, target, bound // 2, min(bound + 1, len(a)-1))

def Binary_Search_interpolation(a, target, low, high):
    
    while low <= high:
        mid = mid = low + (((high - low) // (a[high] - a[low])) * (target - a[low]))
        if a[mid] > target:
            high = mid - 1
        elif  a[mid] < target:
            low = mid + 1
        else:
            return mid
        
        return -1

---

5. Result

다음 이미지는 위 코드를 반복 수행한 결과이다. uniformly distruted한 배열을 쓰지 않으니 interpolation method가 일반 이진탐색과 큰 차이가 없어졌다.