[알고리즘 개념] 이진 탐색

1.  이진탐색이란?

- 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법으로 시작점, 끝점, 중간점을 이용하여 탐색범위를 설정한다.

- 탐색 범위를 절반씩 줄이기 때문에 시간 복잡도는 O(logN)을 보장한다.

 

2. 파이썬 이진 탐색 라이브러리

- bisect_left(a, x) : 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 왼쪽 인덱스를 반환

- bisect_right(a, x) : 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 오른쪽 인덱스를 반환

# 값이 특정 범위에 속하느 ㄴ데이터 개수 구하기
from bisect import bisect_left,bisect_right

# 값이 [lVal, rVal]인 데이터의 개수 반환
def count_by_range(a, lVal, rVal):
  rIdx = bisect_right(a,rVal)
  lIdx = bisect_left(a,lVal)
  return rIdx - lIdx
  
# 배열 선언
a = [1,2,3,3,3,3,4,4,8,9]

# 값이 4인 데이터 개수 출력
print(count_by_range(a,4,4))

# 값이 [-1,3] 범위에 있는 데이터 개수 출력
print(count_by_range(a,-1,3))

 

출력

2
6

 

3. 파라메트릭 서치(Parametric Search)

- 최적화 문제를 결정 문제('예' 혹은 '아니오')로 바꾸어 해결하는 기법

 

# 연습 문제

import sys

input = sys.stdin.readline

n, m = map(int, input().split())
data = list(map(int, input().split()))

# 시작점과 끝점 설정
start = 0
end = max(data)

result = 0
# 이진 탐색 수행
while start <= end:
  total = 0
  mid = (start + end) // 2
  for x in data:
    # 잘랐을 때의 떡의 양 계산
    if x > mid:
      total += x - mid
  # 떡의 양이 부족한 경우 더 많이 자르기 (좌측 탐색)
  if total < m:
    end = mid - 1
  # 떡의 양이 충분한 경우 덜 자르기 (우측 탐색)
  else:
    result = mid  # 최대한 덜 잘랐을 때가 정답이므로, 여기에서 result에 기록
    start = mid + 1

print(result)

 

import sys
from bisect import bisect_left, bisect_right

input = sys.stdin.readline
n, m = map(int, input().split())
data = list(map(int, input().split()))

if m <= max(data):
  lIdx = bisect_left(data, m)
  rIdx = bisect_right(data, m)
  print(rIdx - lIdx)
else:
  print(-1)