[Algo] 이분탐색 문제풀이

기본문제

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
​
#n(원소의 개수)과 target(찾고자 하는 문자열)을 입력 받기
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("존재하지 않음")
else : 
  print(result + 1)

백준 1920 수찾기

import sys
input = sys.stdin.readline
​
N = int(input())
A = list(map(int, input().split()))
M = int(input())
arr = list(map(int, input().split()))
A.sort()    
​
for num in arr:
    lt, rt = 0, N - 1 
    isExist = False 
​
    while lt <= rt: 
        mid = (lt + rt) // 2
        if num == A[mid]: 
            isExist = True  
            print(1)  
            break 
        elif num > A[mid]:  
            lt = mid + 1  
        else: 
            rt = mid - 1
​
    if not isExist:   
        print(0)  

백준 2805 나무자르기

import sys
input = sys.stdin.readline
​
N, M = map(int, input().split())
tree = list(map(int, input().split()))
start, end = 1, max(tree) #이분탐색 검색 범위 설정
​
while start <= end: #적절한 벌목 높이를 찾는 알고리즘
    mid = (start+end) // 2
    
    log = 0 #벌목된 나무 총합
    for i in tree:
        if i >= mid:
            log += i - mid
    
    #벌목 높이를 이분탐색
    if log >= M:
        start = mid + 1
    else:
        end = mid - 1
print(end)