[알고리즘] 이진탐색

순차탐색 : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인
이진탐색 : 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색. 이진탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정한다.

 

재귀:

def binary_search(array,target,start,end):
  if start>end:
    return None
  mid = (start+end)//2
  if array[mid]==target:
    return mid
  elif array[mid]>target:
    return binary_search(array,target,start,mid-1)
  else:
    return binary_search(array,target,mid+1,end)

n, target = list(map(int,input().split()))
array = list(map(int,input().split()))
result = binary_search(array,target,0,n-1)
if result == None:
  print("search fail")
else:
  print('index:',result+1)

 

반복문:

def binary_search(array,target,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
  return None

이진 탐색 라이브러리

from bisect import bisect_left, bisect_right 로

값이 특정 범위에 속하는 데이터 개수 구하기

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

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

from bisect import bisect_left, bisect_right

def count_by_range(array, left_value, right_value):
  right_index = bisect_right(array,right_value)
  left_index = bisect_left(array,left_value)
  return right_index-left_index

 

 

※ 파라메트릭 서치(parametric search): 최적화 문제를 결정문제(예 혹은 아니오)로 바꾸어 해결하는 기법. 예를 들어 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제

 

문제 - 떡볶이 떡 만들기

최적화 문제: 적어도 M만큼의 떡을 얻기 위해  ==> 결정 문제: M 이상인가? 아닌가?의 결정

 

재귀:

n,m=4,6
arr=[19,15,10,17]
max_value = max(arr)
result=[-1]
def bs(result,start,end):
  if start>end:
    print(result[-1])
    return
  mid = (start+end)//2
  total=0
  for i in arr:
    if mid<i:
      total+=i-mid
  if total<m:
    return bs(result,start,mid-1)
  else:
    result.append(mid)
    print(result)
    return bs(result,mid+1,end)
  
bs(result,0,max_value)

반복문

n,m=list(int,input().split())
arr=list(int,input().split())
start=0
end= max(arr)
result=0
while start<=end:
  total=0
  mid=(start+end)//2
  for x in arr:
    if x>mid:
      total+=x-mid
  if total<m:
    end = mid-1
  else:
    result=mid
    start=mid+1

print(result)