본문으로 건너뛰기

이진 탐색 자세히 살펴보기

이진 탐색 자세히 살펴보기

1. 초기 범위 설정

검색 범위의 시작점과 끝점을 설정합니다.

초기 범위 설정
def binary_search(arr, target):
start, end = 0, len(arr) - 1

2. 반복적인 비교 및 범위 조정

중간 요소를 확인하고, 검색 범위를 반으로 줄입니다.

반복적인 비교 및 범위 조정
while start <= end:
mid = (start + end) // 2 # 중간점
if arr[mid] == target: # 찾은 경우
return mid
elif arr[mid] < target: # 중간점의 값보다 찾고자 하는 값이 큰 경우
start = mid + 1
else: # 중간점의 값보다 찾고자 하는 값이 작은 경우
end = mid - 1

return -1 # 찾지 못한 경우

시간 복잡도

  1. 최악의 경우 시간 복잡도: O(log n)

    • 이진 탐색에서는 각 단계마다 검색 범위를 반으로 줄입니다. 따라서, n개의 요소가 있을 때, 최대 log n번의 단계를 거쳐야 합니다.
  2. 최선의 경우 시간 복잡도: O(1)

    • 찾고자 하는 요소가 중간점에 위치하는 경우, 첫 번째 비교에서 바로 찾을 수 있습니다.
  3. 평균 시간 복잡도: O(log n)

    • 대부분의 경우, 이진 탐색은 로그 시간 복잡도를 가집니다. 이는 검색 과정에서 검색 범위가 매 단계마다 반으로 줄기 때문입니다.