def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid # 찾은 경우 인덱스 반환
elif arr[mid] < target:
left = mid + 1 # 오른쪽 절반 탐색
else:
right = mid - 1 # 왼쪽 절반 탐색
return -1 # 찾는 값이 없는 경우
예시
arr = [1, 3, 5, 7, 9, 11, 13]
target = 9
result = binary_search(arr, target)
print(result) # 출력: 4 (인덱스 4에 9가 있음)
정렬되지 않은 배열에서는 사용 불가 (오답 나옴)
중복 값이 있는 경우, 첫 번째 혹은 마지막 인덱스를 원하면 변형된 이분 탐색 필요