이진 탐색
데이터가 정렬되어 있는 상태에서 원하는 값을 찾아내는 알고리즘
- 대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾음
- 시간 복잡도 $O(logN)$
💡 이진 탐색 과정
① 현재 데이터셋의 중앙값(mid)을 선택
② 중앙값 > 타깃 데이터(mid>target)일 때 중앙값 기준으로 왼쪽 데이터셋을 선택(end=mid-1)
③ 중앙값 < 타깃 데이터(mid<target)일 때 중앙값 기준으로 오른쪽 데이터셋을 선택(start=mid+1)
④ ①~③을 반복하다가 중앙값 == 타깃 데이터일 때 탐색 종료
import sys
input = sys.stdin.readline
n = int(input())
A = list(map(int, input().split())) # n개의 정수
A.sort()
m = int(input())
mlist = list(map(int, input().split())) # A에 존재하는지 확인할 m개의 수
for i in range(m):
target = mlist[i] # 찾아야 하는 수
find = 0 # 존재하면 1, 아니면 0
# 이진 탐색
start, end = 0, n-1 # 시작점, 끝점
while start <= end:
mid = (start + end) // 2
if target < A[mid]:
end = mid - 1
elif target > A[mid]:
start = mid + 1
else:
find = 1
break
print(find)# 이진 탐색 함수(재귀적 구현)
def binary_search(array, target, start, end):
if start > end:
return None
mid = (start + end) // 2 # 중간점
if array[mid] == target: # target을 찾았으면 리턴
return mid
elif array[mid] > target: # target이 중간점보다 작으면 왼쪽부분 탐색
return binary_search(array, target, start, mid-1)
elif array[mid] < target: # target이 중간점보다 크면 오른쪽부분 탐색
return binary_search(array, target, mid+1, end)
else:
return None
n = int(input())
A = list(map(int, input().split()))
m = int(input())
B = list(map(int, input().split()))
A.sort()
# B의 요소가 A에 있는지 이진탐색으로 찾기
for i in B:
result = binary_search(A, i, 0, n-1)
if result == None: # A에 없으면 0 출력
print(0)
else: # A에 있으면 1 출력
print(1)
import sys
input = sys.stdin.readline
n, m = map(int, input().split()) # 강의 수, 블루레이 수
time = list(map(int, input().split())) # 강의 길이
answer = 10000
start, end = max(time), sum(time)
while start <= end:
mid = (start + end) // 2
total = 0
count = 0
for i in range(n):
if total + time[i] > mid: # 현재 블루레이에 추가할 수 없으면
count += 1 # 블루레이 개수 +1
total = 0 # 새로운 블루레이 시간 0으로 초기화
total += time[i] # 블루레이에 새로운 강의 영상 추가
if total > 0: # 남은 영상이 있으면 블루레이 개수 +1
count += 1
if count > m:
start = mid+1
else:
end = mid-1
answer = mid
print(answer)
반응형
