Coding Interview Prep · 课时

经典二分查找：左、右、中

Q: 「经典二分查找：左、右、中」课时是免费的吗？

是的 — 「经典二分查找：左、右、中」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。

Q: 「经典二分查找：左、右、中」这节课中我会学到什么？

迭代并递归实现二分查找，准确处理 lo/hi 边界的下标细节，并用边界输入验证正确性。 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

Q: 学习 Coding Interview Prep 需要有经验吗？

无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 1 节课，共 4 节。

Q: 「经典二分查找：左、右、中」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

Q: 我能在这节 Coding Interview Prep 课中编写并运行代码吗？

能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

迭代并递归实现二分查找，准确处理 lo/hi 边界的下标细节，并用边界输入验证正确性。

经典二分查找：左、右、中 是 CoddyKit 上的免费 Coding Interview Prep 课时。这是第 1 节课，共 4 节。你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。

二分查找为何重要

二分查找通过在每一步将搜索空间减半，把 O(n) 的线性扫描降为 O(log n)。在包含一百万个元素的数组中，线性扫描最多需要进行 1,000,000 次比较，而二分查找最多只需要 20 次。这种高效性使它成为编程面试中最常被考查的算法之一。

其核心思想是：有序数组使您能够在一次比较后确定应当完全舍弃剩余数据的哪一半。

左、中、右框架

二分查找使用三个索引指针：lo（左边界）、hi（右边界）和 mid（中点）。每次迭代时，计算 mid = (lo + hi) // 2，并将目标值与 arr[mid] 进行比较。如果目标值更小，则移动 hi = mid - 1；如果更大，则移动 lo = mid + 1；如果相等，则表示已经找到目标值。

循环会在 lo <= hi 时继续执行。如果循环结束时仍未找到目标值，则返回 -1。

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

print(binary_search([1, 3, 5, 7, 9, 11], 7))  # 3
print(binary_search([1, 3, 5, 7, 9, 11], 6))  # -1

避免计算 mid 时的整数溢出

表达式 mid = (lo + hi) // 2 在使用固定位宽整数的语言（Java、C++）中可能导致整数溢出。Python 使用任意精度整数，因此不会发生溢出，但面试官仍希望您了解安全的替代写法：mid = lo + (hi - lo) // 2。

这种写法计算出的中点相同，但它只将半个距离加到 lo 上，而不是先将两个指针相加。在面试中提到这一点，可以体现您对底层问题的了解。

# Safe mid calculation (important in Java/C++, good habit in Python too)
lo, hi = 0, 1_000_000_000
mid_unsafe = (lo + hi) // 2   # fine in Python
mid_safe   = lo + (hi - lo) // 2  # same result, no overflow risk
print(mid_unsafe == mid_safe)  # True

包含端点与不包含端点的边界

二分查找中最棘手的部分之一，是决定 hi 指向最后一个有效索引（包含端点，hi = len(arr) - 1），还是指向末尾之后的位置（不包含端点，hi = len(arr)）。不同的约定需要使用不同的循环条件和边界更新方式。

使用包含端点的边界时，请使用 while lo <= hi，并更新 hi = mid - 1。使用不包含端点的边界时，请使用 while lo < hi，并更新 hi = mid。混用这两种约定，是二分查找实现中最常见的错误来源。

# Exclusive hi variant — useful for bisect-style lower-bound
def search_exclusive(arr, target):
    lo, hi = 0, len(arr)  # hi is one past last
    while lo < hi:          # strictly less than
        mid = lo + (hi - lo) // 2
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid         # NOT mid - 1
    return lo if lo < len(arr) and arr[lo] == target else -1

print(search_exclusive([2, 4, 6, 8, 10], 6))  # 2

递归二分查找

二分查找可以通过递归实现：将更新后的 lo 和 hi 边界通过调用栈传递下去。每次递归调用都会将搜索空间缩小一半，因此深度为 O(log n)。基本情况是 lo > hi（未找到）或 arr[mid] == target（找到）。

生产代码更倾向于使用迭代版本，因为它可以避免调用栈帧的开销；但在白板上，递归版本能够更清晰地表达分治结构。

def binary_search_rec(arr, target, lo, hi):
    if lo > hi:
        return -1
    mid = lo + (hi - lo) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_rec(arr, target, mid + 1, hi)
    else:
        return binary_search_rec(arr, target, lo, mid - 1)

arr = [1, 3, 5, 7, 9, 11]
print(binary_search_rec(arr, 9, 0, len(arr) - 1))  # 4

边界情况：空数组、单个元素

健壮的二分查找必须能够处理边界情况而不会崩溃。最常见的三种情况是：空数组（循环不会执行，并且会正确返回 -1）、只有一个元素的数组（mid、lo、hi 三者相等，一次比较即可完成），以及目标值超出范围（lo 最终会超过 hi，并返回 -1）。

在面试中进入后续问题之前，请务必先用这些输入验证您的实现。

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

print(binary_search([], 5))       # -1  (empty)
print(binary_search([7], 7))      # 0   (single, found)
print(binary_search([7], 3))      # -1  (single, not found)
print(binary_search([1,3,5], 0))  # -1  (below range)
print(binary_search([1,3,5], 9))  # -1  (above range)

时间与空间复杂度

二分查找的时间复杂度为 O(log n)，因为每次比较都会将搜索空间减半。经过 k 次比较后，剩余空间为 n/2^k；当它缩小到 1 时搜索结束，因此 k = log₂ n。

迭代版本的空间复杂度为 O(1)（只使用三个整数变量），递归版本的空间复杂度为 O(log n)，这是由于调用栈的深度所致。在面试中，请始终说明这两种复杂度，并在空间受限时优先使用迭代形式。

import math

for n in [10, 100, 1000, 1_000_000, 1_000_000_000]:
    steps = math.ceil(math.log2(n + 1))
    print(f'n={n:>12,}  max comparisons={steps}')

查找精确匹配还是边界位置

经典二分查找会返回目标值存在时的任意索引。但许多面试题要求查找目标值的首次或末次出现位置。对于这类问题，即使找到匹配项也必须继续搜索——不要立即返回，而是收紧边界并继续查找。

查找首次出现位置时，找到 arr[mid] == target 后，请将 mid 记录为候选位置，并设置 hi = mid - 1。查找末次出现位置时，请设置 lo = mid + 1。

def first_occurrence(arr, target):
    lo, hi, result = 0, len(arr) - 1, -1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] == target:
            result = mid
            hi = mid - 1   # keep searching left
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return result

print(first_occurrence([1, 2, 2, 2, 3], 2))  # 1

使用 Python 的 bisect 模块

Python 标准库提供了 bisect.bisect_left(arr, x) 和 bisect.bisect_right(arr, x)，用于实现可用于生产环境的二分查找。bisect_left 返回能够插入 x 且保持数组有序的最左索引，从而有效地找到第一个满足 arr[i] >= x 的位置。

面试官可能允许您使用 bisect；请务必先确认。了解它的底层工作原理（它是 O(log n) 的二分查找）仍然非常重要。

import bisect

arr = [1, 2, 2, 2, 3, 5]

print(bisect.bisect_left(arr, 2))   # 1  (first 2)
print(bisect.bisect_right(arr, 2))  # 4  (after last 2)

# Check if target exists
target = 3
idx = bisect.bisect_left(arr, target)
print(idx < len(arr) and arr[idx] == target)  # True

二分查找中的常见陷阱

面试中大多数二分查找错误都源于三个问题。第一，循环条件错误：在包含端点的边界中使用 < 而不是 <=，会跳过最后一个剩余元素。第二，边界更新错误：忘记 +1 或 -1，会在 lo == hi 时造成无限循环。第三，操作无序数组：二分查找只有在有序数据上才是正确的。

在编写任何二分查找之前，请先明确说出：“数组已经有序，边界包含端点，并且循环在 lo <= hi 时运行。”

# BUG: infinite loop when lo == hi because hi = mid never moves past lo
def buggy(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo < hi:              # should be lo <= hi for exact-match
        mid = lo + (hi - lo) // 2
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid            # stops, but never returns mid when found
    return lo if arr[lo] == target else -1

print(buggy([1, 3, 5, 7], 7))  # 3 (works here by luck)
print(buggy([1, 3, 5, 7], 1))  # 0 (correct)
print(buggy([1, 3, 5, 7], 4))  # -1 (correct)

二分查找的面试技巧

当您看到涉及有序数组、单调递增函数或可以减半的搜索空间的问题时，请立即考虑二分查找。在面试中，请讲述您的思考过程：“由于数组已经有序，每次比较都可以舍弃一半元素，因此复杂度为 O(log n)。”

请始终至少使用三种输入验证您的解法：开头的值、末尾的值，以及不存在的值。在面试官提问之前主动说明复杂度——“时间 O(log n)，空间 O(1)”——能够体现扎实的基础。

快速检查

请测试您对本课数据结构 & 算法——编程面试准备相关概念的理解。

课程回顾

本课您学到了：二分查找在每一步将搜索空间减半，时间复杂度为 O(log n)；包含端点的边界约定使用 lo <= hi，并通过 lo = mid+1 和 hi = mid-1 更新边界；以及要查找首次或末次出现位置，找到匹配项后仍需继续搜索，而不是立即返回。接下来我们将探索二分查找如何扩展到旋转数组和无序数组。

常见问题解答