본문으로 건너뛰기
실습하기

이진 탐색 자세히 살펴보기

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)

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

다음 내용이 궁금하다면?

코드프렌즈 PLUS 멤버십 가입 or 강의를 등록해 주세요!