Binary search

바이너리 서치는 매우 효율 적이고, 이해하기도 쉽기 때문에 많은 자료구조, 알고리즘 서적의 처음에 등장한다. 구현은 매우 간단하다. 하지만 종종 실수한다. 바이너리 서치와 비슷한 bisect 구현도 추가한다.
구현을 찾아보다 보면 mid 구하는 식에 lo + (hi - lo) // 2 가 쓰이기도 하고, (lo + hi) // 2 이 쓰이기도 한다. 무슨 차이가 있나 싶은데. 차이가 없다. 그런데, 어떤 문제 풀이에서는 식의 선택에 따라서 결과가 달랐던것 같다. (확실하지 않다) 참고로 python stdlib 의 bisect 는 (lo + hi) // 2 를 사용한다.

Binary search

def binSearch(arr, val, lo, hi):
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] == val:
            return mid
        if val < arr[mid]:
            hi = mid - 1
        else:
            lo = mid + 1
    return -1

for _ in range(10000):
    arr = [random.randint(0, 200) for _ in range(10000)]
    arr = sorted(list(set(arr)))
    target = random.randint(0, 200)
    expect = arr.index(target) if target in arr else -1
    actual = binSearch(arr, target, 0, len(arr) - 1)
    assert expect == actual

Greatest smaller than x

def greatestSmall(arr, val, lo, hi):
    while lo <= hi:
        mid = (hi + lo) // 2
        if arr[mid] < val:
            lo = mid + 1
        else:
            hi = mid - 1
    return hi

from bisect import bisect_left

# Test
for _ in range(10000):
    arr = [random.randint(0, 4000) for _ in range(1000)]
    arr = sorted(list(set(arr)))
    target = random.randint(0, 4000)
    actual = greatestSmall(arr, target, 0, len(arr) - 1)
    expect = bisect_left(arr, target) - 1
    assert actual == expect