P4771 找苹果（基础）

小鹿有一堆苹果，重量已经从小到大排好了。大熊想知道这堆苹果里有没有 m 克的苹果，要求用二分法快速判断，有就输出 YES，没有就输出 NO。

解题思路

1. 苹果已经排好序。 题目保证苹果重量从小到大排列，所以可以直接用二分法在数组里找 m。

2. 二分查找的核心。 设 low 指向数组开头（下标 0），high 指向数组末尾（下标 n - 1）。每次取 mid = (low + high) / 2 看 appleWeight[mid] 和 m 的大小：相等就找到了；比 m 大就往左半边找（high = mid - 1）；比 m 小就往右半边找（low = mid + 1）。如果 low 超过了 high 还没找到，就说明 m 克重的苹果不存在。

3. 数据量很大。 n 最多接近一千万，用普通输入会太慢，所以要用快速读入：用 fread 把一大块数据读进缓冲区，再一个个解析成数字。

4. m 可能是负数。 测试数据里 m 可能是负数，比如 -58。快速读入时要注意负号，把 -58 读成负的 58，再放进全是正数的苹果堆里二分查找，自然找不到，输出 NO。

5. 输出。 找到输出 "YES"，找不到输出 "NO"。

参考代码

// 找苹果：n个苹果重量从小到大排好，用二分查找判断是否有m克的苹果
#include <cstdio>
using namespace std;
int appleWeight[10000000]; // 全局数组保存每个苹果的重量

const int BUFFER_SIZE = 1 << 20; // 输入缓冲区大小
char readBuffer[BUFFER_SIZE];
int readPos = 0, readLength = 0;
// 快速读入一个整数（苹果个数最多接近一千万，读入量大，必须用快速读入；m可能是负数，要处理符号）
int fastRead(){
    int num = 0;
    int sign = 1; // 正负号，默认正数
    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; // 跳过空白，找到第一个数字
        if(c == '-') sign = -1;          // 记下负号
    }
    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 * sign;
}

int main(){
    int n = fastRead(); // 苹果个数
    for(int i = 0; i < n; i++){
        appleWeight[i] = fastRead(); // 读入每个苹果的重量
    }
    int target = fastRead(); // 想找的重量
    int low = 0, high = n - 1;
    int found = 0; // 是否找到
    // 二分查找m克的苹果
    while(low <= high){
        int mid = (low + high) / 2;
        if(appleWeight[mid] == target){
            found = 1;
            break;
        } else if(appleWeight[mid] > target){
            high = mid - 1; // 重量太大，往左半边找
        } else {
            low = mid + 1;  // 重量太小，往右半边找
        }
    }
    if(found) printf("YES\n");
    else printf("NO\n");
    return 0;
}

复杂度分析

每次二分都把查找范围缩小一半，n 最多接近 10^7，二分最多只要 log2(10^7) ≈ 24 次比较，时间复杂度是 O(log n)，非常快。读入全部数据的时间是 O(n)。空间上用一个长度为 n 的全局数组存苹果重量，空间复杂度是 O(n)。