이분 탐색 문제 해결 전략

이분 탐색 알고리즘은 정렬되어 있는 리스트에서 탐색 범위를 전발씩 좁혀가며 데이터를 탐색하는 방법이다.

시간 복잡도는 NlongN이다.

def binary_search(left, right, array, target):
	while left <= right:
    	mid = (left + right) // 2
        if array[mid] == target:
        	return mid
        elif array[mid] > target:
        	right = mid - 1
        else:
        	left = mid + 1

이분 탐색 알고리즘이다.

 

보통 PS에서 이분 탐색을 적용하는 방법은 완전 탐색을 해야 하는 문제 O(N^2)를 NlogN으로 해결하는 과정에서 많이 쓰인다.

아래의 두 문제 예시를 보자 

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

백준 중량 제한 문제에서도 완전 탐색의 풀이 즉 최대 중량을 1부터 최대 까지 하나씩 순회하며 가능한 중량을 찾는 완전 탐색 알고리즘에서 최대 중량을 이분 탐색으로 logN으로 시간 복잡도를 줄여 NlongN으로 문제를 해결한다.

또 

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

백준의 공유기 설치문제 또한  공유기를 설치할 때 완전 탐색으로 최소 거리를 1부터 최대 거리까지 순회하며 완전 탐색으로 풀이하는 알고리즘 대신 1부터 최대 거리를 이분 탐색으로 logN으로 순회하며 NlogN으로 문제를 해결한다.