P4777 查找一个数是否存在（基础）

在一个递增且没有重复元素的数组里，找出 x 的位置（位置从 1 开始编号）。如果 x 在数组中不存在，输出 -1。

解题思路

1. 数组已经从小到大排好。 而且没有重复元素，所以可以放心使用二分查找，不用一个个从头找。

2. 二分找位置。 low = 0，high = n - 1。每次取 mid = (low + high) / 2，比较 numArray[mid] 和 x：相等就找到了，位置是 mid + 1（因为题目要求位置从 1 开始编号）；中间的数比 x 大，就往左半边找（high = mid - 1）；比 x 小就往右半边找（low = mid + 1）。

3. 找不到输出 -1。 如果 low 超过了 high 还没有找到，就说明数组里没有 x，输出 -1。

4. 数据量很大。 n 最大 5×10^6，用普通输入可能超时，必须用快速读入：用 fread 把数据读进缓冲区，再一个个解析成整数。

5. 具体例子。 数组是 1 3 5 7 9 11 13 15 17 19，找 3。第一次 mid 指向第 5 个数 9，比 3 大，去左半边；第二次 mid 指向 3，正好找到，位置是 2，输出 2。

参考代码

// 查找一个数是否存在：在递增数组中用二分查找x的位置，不存在输出-1
#include <cstdio>
using namespace std;
int numArray[5000005]; // 全局数组保存递增数组

const int BUFFER_SIZE = 1 << 20; // 输入缓冲区大小
char readBuffer[BUFFER_SIZE];
int readPos = 0, readLength = 0;
// 快速读入一个整数（n最大五百万，读入量大，必须用快速读入）
int fastRead(){
    int num = 0;
    char c;
    while(true){
        if(readPos >= readLength){
            readLength = fread(readBuffer, 1, BUFFER_SIZE, stdin);
            readPos = 0;
        }
        c = readBuffer[readPos++];
        if(c >= '0' && c <= '9') break; // 跳过空白，找到第一个数字
    }
    while(c >= '0' && c <= '9'){
        num = num * 10 + (c - '0');
        if(readPos >= readLength){
            readLength = fread(readBuffer, 1, BUFFER_SIZE, stdin);
            readPos = 0;
        }
        c = readBuffer[readPos++];
    }
    return num;
}

int main(){
    int n = fastRead(); // 数组元素个数
    for(int i = 0; i < n; i++){
        numArray[i] = fastRead();
    }
    int x = fastRead(); // 要查找的数
    int low = 0, high = n - 1;
    int answer = -1; // 默认找不到，输出-1
    // 二分查找x的位置
    while(low <= high){
        int mid = (low + high) / 2;
        if(numArray[mid] == x){
            answer = mid + 1; // 找到，位置从1开始编号
            break;
        } else if(numArray[mid] > x){
            high = mid - 1; // 中间的数太大，往左半边找
        } else {
            low = mid + 1;  // 中间的数太小，往右半边找
        }
    }
    printf("%d\n", answer);
    return 0;
}

复杂度分析

n 最大 5×10^6，二分查找每次把范围减半，最多 log2(5×10^6) ≈ 23 次比较，时间复杂度是 O(log n)。读入全部数据需要 O(n) 时间。空间上用一个数组存全部元素，空间复杂度是 O(n)。