(python) 이진 탐색(이분 탐색) ex 2110번

이진 탐색(이분 탐색)이란

컴퓨터과학, 수학 등에서 오름차순으로 정렬된 정수의 리스트를 같은 크기의 두 부분 리스트로 나누고 필요한 부분에서만 탐색하도록 제한하여 원하는 원소를 찾는 알고리즘이다.

 

대부분 정렬되어 있는 수들에 대해서 타깃을 찾을 때 중간 부분(mid)을 기준으로

1. start와 end를 설정함 중간(start + mid) // 2를 기준으로 탐색

mid < 타깃일 때 start를 mid값으로 하여 다시 탐색

mid > 타깃일 때 end를 mid값으로 하여 다시 탐색

 

즉 탐색 범위를 절반씩 좁혀가며 값을 탐색하기에 시간복잡도는 O(logN)

 

파이썬으로는 재귀함수나 반복문을 사용할 수 있고, 이진 탐색 라이브러리를 사용할 수도 있다.재귀함수 (low = start, high = end)

def binarySearch(array, value, low, high):
	if low > high:
		return False
	mid = (low+high) / 2
	if array[mid] > value:
		return binarySearch(array, value, low, mid-1)
	elif array[mid] < value:
		return binarySearch(array, value, mid+1, high)
	else:
		return mid

반복문

def binarySearch(array, value, start, end):
	while start <= end:
    	mid = (start + end) // 2
        if array[mid] == target:
        	return mid
        elif array[mid] > target:
        	end = mid - 1
        else:
        	start = mid + 1

이진 탐색 라이브러리

from bisect import bisect_left, bisect_right

bisect_left(a, x) # 배열 a에 x를 삽입할 가장 왼쪽 인덱스 반환
bisect_right(a, x) # 배열 a에 x를 삽입할 가장 오른쪽 인덱스 반환

 

예시로 좋은 문제 boj 2110

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

1. 리스트에 집의 위치를 넣고 정렬해준다.

 

2. 시작과 끝은 사이의 거리가 될 수 있는 최솟값과 최댓값으로 설정한다.

start = 1 

end = 리스트[N-1] - 리스트[0]

 

3.1 공유기가 2개인 경우는 바로 end를 출력하면 된다.

 

3.2 반복문 while을 이용하여 이진탐색을 할 것인데 반복문 조건이 중요하다. 

start <= end로 하여 반복문을 탈출한다.

mid = (start + end) // 2

공유기 개수를 세어줄 변수 count

공유기를 마지막 설치한 위치를 저장할 변수는 wifi_index로 정했다.

 

count가 목표인 C보다 크거나 같으면

출력할 정답 변수 result에 mid값을 넣고

start값에 mid + 1을 넣어 다음 탐색을 중간에서 끝으로 잡는다.

 

count가 목표인 C보다 작으면

end값에 mid - 1을 넣어 다음 탐색을 처음에서 중간으로 잡는다.

 

import sys

N, C = map(int, input().split())

array = [int(sys.stdin.readline()) for _ in range(N)]

array.sort()
start = 1
end = array[N - 1] - array[0]
result = 0

if C == 2:
  print(end)
else:
  while(start <= end):
    mid = (start + end) // 2
    count = 1 ## 공유기 갯수
    wifi_index = array[0] ## wifi_index 마지막 설치한 위치
    for i in range(N):
      if (array[i] - wifi_index) >= mid:
        count += 1
        wifi_index = array[i]
    if count >= C:
      result = mid
      start = mid + 1
    else:
      end = mid - 1
  print(result)