解题思路

题目要求在一个递增数组里用二分查找找某个数 x 的位置。

什么是二分查找？

数组是递增排好序的，所以可以每次看中间的数：

• 如果中间的数比 x 大，说明 x 在左半边
• 如果中间的数比 x 小，说明 x 在右半边
• 如果相等，就找到了

每次把查找范围缩小一半，所以很快。

步骤：

1. 设查找范围是 l 到 r，初始是整个数组
2. 取中间位置 mid = (l+r)/2
3. 比较 a[mid] 和 x：
   • a[mid] > x：x 在左边，r = mid-1
   • a[mid] < x：x 在右边，l = mid+1
   • 相等：输出 mid，结束
4. 如果 l > r 还没找到，说明 x 不存在，输出 -1

为什么这么快？ n=10^6 时，二分查找最多只要 20 次左右（因为 2^20 ≈ 100万），比一个个找快得多。

参考代码

#include <iostream>
using namespace std;

int a[1000005], n, x, mid;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    cin >> x;

    int l = 1, r = n;

    while (l <= r) {
        mid = (l + r) / 2;
        if (a[mid] > x) {
            r = mid - 1;
        } else if (a[mid] < x) {
            l = mid + 1;
        } else {
            cout << mid;  // 找到
            return 0;
        }
    }

    cout << -1;  // 没找到
    return 0;
}

复杂度分析

• 时间复杂度：O(log N)，每次范围减半
• 空间复杂度：O(N)，存数组