[알고리즘] 이분탐색 Binary Search

이분 탐색(binary search)

• 순차 탐색 O(n)의 시간 복잡도를 O(logn)으로 줄일 수 있다.
• 오름차순으로 정렬된 정수의 리스트에서 특정 데이터를 찾기 위해 탐색 범위를 절반으로 좁혀가면서 탐색하는 방법

 

이분 탐색 문제 - 1920번 수 찾기 

https://www.acmicpc.net/problem/1920

1920번: 수 찾기

 

n = 5
a = [4, 1, 5, 2, 3]
m = 5
b = [1, 3, 7, 9, 5]
a = sorted(a)
maxVal = a[-1] # 최대값

for element in b:
    lt = 0
    rt = n - 1
    res = 0

	# 최대값보다 구해야하는 수가 작은 경우만 이분 탐색
    if maxVal >= element:
        while lt <= rt:
            mid = (lt + rt) // 2
            print(element, lt, rt, mid, a[mid], res)
            if a[mid] == element:
                res = 1
                break
            elif a[mid] < element:
                lt = mid +1
            else:
                rt = mid -1
    print(res)

 

이분 탐색 문제 - 1654번 랜선 자르기

https://www.acmicpc.net/problem/1654

1654번: 랜선 자르기

 

# k, n = 4, 11  # 이미 가지고 있는 랜선 개수, 필요한 랜선 개수 n
# kArr = [802, 743, 457, 539] # 랜선은 길이가 모두 다르다.
k, n = map(int, input().split())
kArr = []

for i in range(k):
    kArr.append(int(input()))
kArr = sorted(kArr) # 이분 탐색을 위한 정렬
lt = 0
rt = kArr[-1]
maxLen = 0

while lt <= rt:
    mid = (lt+rt)//2
    total = 0
    for size in kArr: # 구할 수 있는 랜선 개수 구하기
        total += (size//mid)

    if total >= n: # 랜선의 개수가 더 많을 경우
        maxLen = max(maxLen, mid) # 최대값 갱신
        lt = mid +1
    else:
        rt = mid -1 # 랜선의 개수가 부족할 경우 
print(maxLen)

 

이분 탐색 문제 - 2110번 공유기 설치

https://www.acmicpc.net/problem/2110

2110번: 공유기 설치

import sys

n, c = map(int, sys.stdin.readline().split())  # 집의 개수, 공유기 개수
x_arr = []

for _ in range(n):
    x = int(sys.stdin.readline())  # 집의 좌표
    x_arr.append(x)

x_arr.sort()

res = 0
start = 1  # 최소 거리 1
end = x_arr[-1] - x_arr[0]  # 최대 거리 = 가장 먼거리

while start <= end:
    mid = (start + end) // 2  # 중간값 = 현재 가능한 공유기 사이의 거리
    temp = x_arr[0]  # 이전 집의 좌표
    cnt = 1

    for i in range(1, n):
        if x_arr[i] - temp >= mid:  # 가능한 거리(mid) 이상으로 공유기를 설치할 수 있는 집에 공유기 설치
            cnt += 1
            temp = x_arr[i]

    if cnt >= c:  # c개 이상의 공유기를 설치할 수 있는지 확인
        start = mid + 1  # 가능하면 mid 증가
        res = mid
    else:
        end = mid - 1  # 불가능하면 mid 감소

print(res)