이분탐색 알고리즘

배열이 크기순으로 정렬되어 있을때 O(logN) 시간에 값의 위치를 탐색할 수 있는 알고리즘. 배열이 크기순으로 정렬되어 있기에 구역을 절반씩 나눠 원하는 값이 어떤 영역에 있는지 탐색을 반복해 위치를 특정한다.

logN의 시간복잡도가 얼마나 강력한지 설명하자면 N이 long타입의 최고 범위 10^18이라고 가정하더라도, O(log10^18) = O(18*log10) = 약 54. 무려 상수에 가깝게 줄어든다. 즉 억을 넘어 경단위의 문제도 풀이 가능하다.

이분탐색 알고리즘의 유형

이분탐색 알고리즘은 크게 2가지 목적으로 사용할 수 있다.
1. 정렬된 배열에서 특정 값 인덱스 탐색
2. 정렬된 배열에 값을 들어갈 인덱스 탐색

이분탐색 종류

정답일 수 있는 구간 표현을 left는 닫히게 right는 열린 형태로 잡고 구현하는 방법을 설명한다.

Lower bound: target 이상의 값이 나오는 처음 인덱스 반환

def lower_bound(arr, target):
    l = 0
    r = len(arr)   # [l, r)

    while l < r:
        mid = l + (r - l) // 2

        if arr[mid] < target: # 핵심 차이점
            l = mid + 1
        else:
            r = mid

    return l

Upper bound: target 초과 값이 나오는 처음 인덱스 반환 (Lower에서 등호하나만 넣어서 구현했다.)

def upper_bound(arr, target):
    l = 0
    r = len(arr)   # [l, r)

    while l < r:
        mid = l + (r - l) // 2

        if arr[mid] <= target:
        	l = mid + 1
        else:
            r = mid

    return l

구현에 대한 팁

• 파라매트리 서치는 위 코드를 그대로 활용해서 풀이 가능하다.

첫번째 false찾기 (true는 당연히 not연산 한번이면 동일하다)

# T T T F F 패턴인 경우로 가정
def parametric(l, r, ok):
    # [l, r)
    while l < r: # 여기에 등호가 없는 이유는 l == r인 경우 후보가 없기 때문이다. 더 진행하면 안됌 (반례는 단일 F인 경우)
        mid = l + (r - l) // 2

        if ok(mid):
        	l = mid + 1
        else:
			r = mid

    return l

• mid를 계산하는 과정에서 left와 right를 합하기에 overflow에 주의한다.
  해당 식으로 예방도 가능하다.

mid = left + (right - left) / 2

• 주로 구현이 제대로 되었는지 확인하는 방법은 조건문이 아래와 같은 경우에 정상적인 정답을 구하는가 확인하면 된다.

// 1을 찾는 문제인 경우
{0} // 정답이 없는 경우가 있다면 이것도 확인해줘야 한다.
{1} // 정답을 제대로 출력하는지 확인 + 경계값 첫번째 원소인 경우
{0, 1} // 경계값 마지막 원소인 경우
{0, 1, 1, 2} // upper, lower가 제대로 적용되었나 확인