PostsSeriesLabsAlgo

탐색

이분 탐색

업-다운 게임 잘하는 법

제가 1~100 중 하나를 정했습니다. 몇 번 만에 맞히는지 해 보세요.

1남은 후보 100개100

50

    가운데를 부르면 절반이 날아갑니다. 어느 쪽 답이 오든 똑같습니다.

    100 → 50 → 25 → 13 → 7 → 4 → 2 → 1일곱 번. 운이 나빠도 일곱 번.

    매번 절반씩 버리는 방법 = 이분 탐색

    이분 탐색은 정렬된 줄에서만 쓸 수 있다

    • 버릴 수 있던 이유 — 왼쪽이 전부 더 작다고 알기 때문
    • 섞여 있으면 — 가운데가 작아도 왼쪽에 큰 수가 있다. 못 버린다
    • 신호— 문제에 “오름차순으로 주어진다”

    코드는 방금 한 게임을 그대로 옮긴 것이다

    배열에서 42 찾기. 다음을 눌러 한 줄씩 넘겨 보세요.

    다음을 눌러 한 줄씩 넘겨 보세요

    left = 0 right = 9

    binary_search.py
    1. 1def binary_search(arr, target):
    2. 2 left, right = 0, len(arr) - 1
    3. 3 while left <= right:
    4. 4 mid = (left + right) // 2
    5. 5 if arr[mid] == target:
    6. 6 return mid
    7. 7 elif arr[mid] < target:
    8. 8 left = mid + 1
    9. 9 else:
    10. 10 right = mid - 1
    11. 11 return -1
    0 / 15
    • left right — 아까 막대의 양 끝
    • mid — 여러분이 부른 수

    42 대신 12를 찾는다면, 첫 질문 뒤에 어느 쪽이 버려질까요?

    이분 탐색은 경계에서 틀린다

    • <= 에서 등호를 빼면 — 한 칸 남았을 때 그 칸을 안 본다. 있어도 “없다”
    • mid + 1 에서 +1 을 빼면 — 범위가 안 줄어든다. 무한 루프

    위 플레이어에서 한 칸 남는 순간을 다시 돌려 보세요. 전부 거기서 틀립니다.

    이분 탐색을 꺼내라는 세 가지 신호

    정렬돼 있다값 하나를 찾는다N이 너무 크다

    다음 장에서는 찾는 값이 여러 개일 때 그중 첫 번째를 어떻게 찾는지 봅니다.