이분탐색

어떤 T(Target)가 배열 A에 존재하는 위치를 빠르게 찾을 때 선형탐색으로 찾을 수 있다.

pos = -1
for i in range(len(A)):
    if A[i] == T:
        pos = i
        break
print(pos) # T의 값이 존재, -1이라면 존재하지 않는다.

worst case(존재하지 않는 경우 포함)가 $O(n)$이므로 탐색치고 좋지 않은 방법이다.

만약 배열이 이미 정렬 되어있다면?(자연수도 배열이라고 생각할 수 있다.)
절반씩 끊어서 T보다 크면 T는 오른쪽에, 작다면 T는 왼쪽에 있을것이라고 기대할 수 있다.

def binary_search(A, T):
    # 시작 인덱스 지정
    start, end = 0, len(A) - 1
   
    while start <= end:
        mid = (start + end) // 2
        if A[mid] == T:
            return mid
        elif A[mid] > T:
            end = mid - 1
        else:
            start = mid + 1
    
    # T가 배열 A에 존재하지 않음
    return -1

그리고 1변수 방정식, 부등식의 해를 구할수 있다.
방정식의 해 구하기 참고
이분탐색을 이용하는 2가지 방법이다.

1. 빠른 탐색(원소의 존재성)
2. 방정식, 부등식의 해

상한선(Upper Bound)

다음과 같은 문제를 생각하자.

정렬되어있는 배열에서 처음으로 T보다 큰 값이 나오는 위치는?
예) A = [1 1 1 2 2 2 4 4 6 6 7 8 10]에서 5보다 큰 값이 나오는 위치는 8이고 그 값은 A[8]=6 이다.

우선 A[mid]에 T가 존재한다고 해보자. 이때 mid가 T를 만족하는 최솟값이 아닐 수 있다. 따라서 start = mid + 1로 하고 이분탐색을 더 진행한다

A[mid] > T라고 하자. mid가 크므로 end를 줄일것인데 이때 mid가 처음으로 T보다 큰 위치일 수 있다. 따라서 end = mid - 1이 아니라 end = mid로 한다. (이때 end는 정답의 후보값이 된다.)

A[mid] < T라고 하자. mid가 작으므로 start를 크게한다. start = mid + 1이다.

start, end = 0, len(A)  # len(A)-1이 아니다. 이유는 아래에
while start < end:
    mid = (start + end) // 2
    if A[mid] == T:
        start = mid + 1
    elif A[mid] > T:
        end = mid
    else:
        start = mid + 1

# loop가 끝나면 end가 후보값이다
# end == len(A)라면 답이 없다는 뜻이다. (T >= A_max)

하한선(Lower Bound)

다음과 같은 문제를 생각하자.

정렬되어있는 배열에서 처음으로 T 이상이 나오는 위치는?
예) A = [1 1 1 2 2 2 4 4 6 6 7 8 10]에서 처음으로 3 이상이 나오는 위치는 6이고 A[6] = 4이다.

상한선과 묘하게 문제가 다르다

만약 A[mid] == T라 하자. mid가 T가 처음 나오는 위치가 아닐 수도 있으므로 end = mid - 1이 아니라 end = mid이다. (이때 end는 후보값이 된다.)

start, end = 0, len(L)
while start < end:
    mid = (start + end) // 2
    if A[mid] == T:
        end = mid
    elif A[mid] > T:
        end = mid
    else:
        start = mid + 1

[BOJ 3079] 입국심사

시간이 T분일때, 각 심사대에서 몇명의 사람을 통과시켰는지를 $f(T)$라 하자. 그러면 $f(T) \ge M$인 $T_{min}$을 구하는 것이 정답이 된다. 하한선 탐색을 하면 된다. 아래 코드에서 $f(T)$를 total로 직접 계산했다. 자연수도 이미 정렬되어있는 배열로 볼 수 있기때문에 이분탐색으로 풀이가 가능하다.

import sys
N, M = map(int, input().split())
L = list(int(sys.stdin.readline()) for _ in range(N))

start, end = 0, max(L) * M

# find Lower Bound
while start < end:
    mid = (start + end) // 2
    
    # f(x) 계산, f(x) >= M인 x의 최솟값이 정답이다
    total = 0
    for x in L:
        total += mid // x

    if total == M:
        end = mid
    elif total < M:
        start = mid + 1
    else:
        end = mid
print(end)

[BOJ 2512] 예산

현재 기준 예산을 $x$, 최대 예산을 $L$이라 했을때 전체예산을 $f(x)$라 하면, $f(x) \le L$이 되는 $x_{max}$가 정답이다. 상한선 코드를 이용하되, 후보값은 $f(x)=L$일 때와 $f(x)<L$일 때 이렇게 2군데에서 생긴다. 즉, 후보값 갱신(해 갱신)은 $f(x) \le L$일때 조정해준다.

N = int(input())
L = list(map(int, input().split()))
limit = int(input())

ans = -1 # 정답 후보값
start, end = 0, max(L) + 1
while start < end:
    mid = (start + end) // 2
    
    # 전체 예산 계산
    total = 0
    for x in L:
        if x >= mid:
            total += mid
        else:
            total += x
    
    # 후보값 갱신과 구간 갱신
    if total > limit:
        end = mid
    else:
        ans = mid
        start = mid + 1
print(ans)