리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인
.1. 정렬되어 있는 리스트에서 범위를 절반씩 좁혀가며 데이터 탐색
2. 시작점, 끝점, 중간점을 이용하여 범위 설정
# 이진탐색 재귀 ver
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('원소가 존재하지 않습니다.')
else:
print(result + 1)
# 이진탐색 반복 ver
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 = 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)
from bisect import bisect_left, bisect_right
a = [1, 2, 4, 4, 8]
x = 4
print(bisect_left(a, x))
print(bisect_right(a, x))
- 최적화 문제를 결정 문제로 바꾸어 해결하는 기법
- 특정한 조건을 만족한느 가장 알맞은 값을 빠르게 찾는 최적화 문제
- 파라메트릭 서치는 이진 탐색을 이용해 해결