[딩코딩코 2025 코딩테스트 필수 알고리즘] - 6. 이진탐색

본 글에 사용된 코드와 이미지의 일부는
딩코딩 님의 『38군데 합격 비법, 2025 코딩테스트 필수 알고리즘』 강의를 참조하여 발췌·활용하였습니다.

[본 게시물은 파트너스 활동의 일환으로 소정의 수수료를 받을 수 있습니다.] https://inf.run/tXMrp\

---

이진 탐색 vs 순차 탐색

특정 숫자를 맞추는 게임인 업다운 게임을 생각해보자. 가장 좋아하는 숫자, 끌리는 숫자, 1부터 차근차근 등 특정 숫자를 맞추는데 다양한 방식이 있을 것이다.

알고리즘 관점에서 보면 가장 효율적인 방법은 범위의 절반인 50을 시도 해보는 것이다. 대답이 UP 이라면 1~49 는 후보에서 없어지고, 대답이 DOWN 이면 51~100 이 후보에서 없어진다.

이 방법을 이진 탐색이라고 한다.

순차 탐색

그러면 순차 탐색과 이진 탐색 중 어느 방식이 더 효율적일까?

우선 순차 탐색의 코드를 살펴보자.

finding_target = 14
finding_numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]

def is_existing_target_number_sequential(target, array):
    find_count = 0
    for number in array:
        find_count += 1
        if target == number:
            print(find_count) # 14!
            return True

    return False

result = is_existing_target_number_sequential(finding_target, finding_numbers)
print(result)  # True

배열을 차례로 따라가면서 찾다보니, 검색 횟수가 총 14번이 나온다. 만약 찾는 숫자가 20 이였다면, 20번 검색해야 했을테니, 최악의 경우는 O(N) 걸린다고 할 수 있다.

이진 탐색

그럼 이진 탐색을 살펴보자.

finding_target = 14
finding_numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]

def is_existing_target_number_binary(target, array):
    current_min = 0
    current_max = len(array) - 1
    current_guess = (current_min + current_max) // 2

    find_count = 0
    while current_min <= current_max:
        find_count += 1
        if array[current_guess] == target:
            print(find_count)  # 3!
            return True
        elif array[current_guess] < target:
            current_min = current_guess + 1
        else:
            current_max = current_guess - 1
        current_guess = (current_min + current_max) // 2

    return False

result = is_existing_target_number_binary(finding_target, finding_numbers)
print(result)

만약 UP 이라면? 9 ~ 16을 시도하고, 만약 DOWN 이라면? 1 ~ 7을 시도하고, 만약 정답이라면? True 를 반환하면 된다.

위와 같이 하기 위해서는 최솟값, 최댓값, 시도하는 인덱스 값 을 변수로 설정하면 된다. 그리고 시도했을 때 target 보다 작다면, 더 큰 값을 살펴봐야 하니까 최솟값에 시돗값 + 1 을 해주면 된다. target 보다 크다면, 더 작은 값을 살펴봐야 하니까 최댓값에 시돗값 - 1 을 해주면 된다. 이를 최솟값≤ 최댓값 까지 반복해야 한다. < 가 아니라 ≤ 인 이유는 최솟값 == 최댓값 시점까지 확인을 해야 하기 때문이다.

이진 탐색의 시간 복잡도

총 숫자가 1 ~ N 까지라고 한다면 1번 탐색 → N/2 , 2번 탐색 → N/4 , 3번 탐색 → N/8 … k번 탐색 → N/2^k 개가 남게 된다.

이 때, 이분 탐색을 열심히 시도해서 딱 1개만 남았다고 해보자. 수식으로 표현하면 N/2^k = 1 이다.

즉, $k = \log_2{N}$ 횟수를 시도하면 정답을 찾을 수 있다. 결론적으로 이분 탐색을 위해서는 시간 복잡도가 O(log N) 만큼 걸린다.

여기서 왜 $log_2N$ 이 아니라 $logN$ 인 이유는 상수는 무시해도 되기 때문에 표기하기 쉽도록 $logN$ 으로 약속했다.