二分查找（Binary Search）

---

1. 算法本身描述（要点）

二分查找用于在已按升序排列的有序数组中查找给定元素 key。基本思想是：每次比较待查元素与当前区间中点元素的大小，根据比较结果把查找区间缩为原来的一半，直到找到或区间为空。

预置条件：数组必须有序（升序），索引通常用 0..n-1。

核心步骤（迭代版）：

1. 令 low = 0, high = n-1。
2. 当 low <= high 时：
   • 计算中点 mid = low + (high - low) / 2（防止溢出）。
   • 若 arr[mid] == key，返回 mid（找到）。
   • 若 arr[mid] < key，则 low = mid + 1（在右半区继续查找）。
   • 若 arr[mid] > key，则 high = mid - 1（在左半区继续查找）。
3. 若循环结束仍未找到，返回 -1 表示不存在。

正确性要点（不做完全证明，只说明直观不变式）：

• 循环不变式：查找目标若存在，必位于区间 [low, high] 中。每次迭代这个区间严格缩小，最终缩为空或找到目标。

注意与变体：

• 如果数组含重复元素，上述实现返回的是某个匹配位置，不保证是第一个或最后一个出现的位置。若需要“最左/最右”的索引，可在比较后调整更新策略（见下方备注）。
• 递归实现也常见，递归深度为 O(log n)（会占用额外栈空间）。

---

2. C 语言实现

#include <stdio.h>

/*
 * 二分查找（迭代）
 * 参数:
 *   arr   - 指向升序排列整数数组的指针
 *   n     - 数组长度（元素个数）
 *   key   - 要查找的目标值
 * 返回值:
 *   如果找到，返回目标在数组中的下标（0-based）
 *   如果未找到，返回 -1
 */
int binary_search(const int arr[], int n, int key) {
    int low = 0;
    int high = n - 1;

    while (low <= high) {
        /* 防止 (low + high) 溢出，使用 low + (high - low) / 2 */
        int mid = low + (high - low) / 2;

        if (arr[mid] == key) {
            return mid; /* 找到 */
        } else if (arr[mid] < key) {
            low = mid + 1; /* 在右半区继续 */
        } else {
            high = mid - 1; /* 在左半区继续 */
        }
    }

    return -1; /* 未找到 */
}

/* 简单测试 */
int main(void) {
    int a[] = {1, 3, 5, 7, 9, 11, 13};
    int n = sizeof(a) / sizeof(a[0]);
    int targets[] = {7, 2, 13, 1, 14};
    int m = sizeof(targets) / sizeof(targets[0]);

    for (int i = 0; i < m; i++) {
        int t = targets[i];
        int idx = binary_search(a, n, t);
        if (idx != -1) {
            printf("查找 %d：找到，下标 = %d\n", t, idx);
        } else {
            printf("查找 %d：未找到\n", t);
        }
    }

    return 0;
}

代码说明要点

• 使用 low + (high - low) / 2 避免 low + high 在整型边界时溢出。
• 返回 -1 作为未找到的标识，符合常见约定。
• 迭代版占用常数额外空间；递归版代码更简洁但会使用栈空间。

（若需要“查找第一个等于 key 的位置”或“查找最后一个等于 key 的位置”，可将相等时不立即返回，而是推动区间向左或向右直到找到边界——可在后续补充。）

---

3. 时空复杂度分析

• 时间复杂度（Time Complexity）
  • 最坏情况（worst-case）：O(log n)。每次比较将查找区间缩小为原来的一半，因此最多进行约 ⌊log2 n⌋ + 1 次比较。
  • 平均情况（average-case）：O(log n)。
  • 最好情况（best-case）：O(1)（中点即为目标）。
• 空间复杂度（Space Complexity）
  • 迭代实现：O(1)（常数额外空间）。
  • 递归实现：O(log n)（递归调用栈深度约 log n）。

---

附：常见陷阱与考点

1. 数组必须有序：若输入未排序，二分查找不成立。考题常要求先排序或说明已排序。
2. 溢出：中点计算若写成 (low + high) / 2 在某些语言/场景可能溢出，教材常强调用 low + (high - low) / 2。
3. 重复元素：考试可能要求找“第一个≥key”或“最后一个≤key”等区间边界问题，需要微调边界移动策略（利用 low <= high 的循环不变式来推导）。
4. 下标与长度/空数组：空数组 n == 0 时要保证 high = -1，循环条件 low <= high 会直接退出，返回 -1。