二分查找

#include <iostream>
#include <vector>
using namespace std;

// 在有序数组 a 中查找 target，返回下标；找不到返回 -1
int binarySearch(vector<int>& a, int target) {
    int lo = 0;             // 搜索区间的左端点
    int hi = a.size() - 1;  // 搜索区间的右端点

    while (lo <= hi) {  // 区间不为空，就继续找
        // 计算中间位置
        // 用 lo + (hi - lo) / 2 而不是 (lo + hi) / 2 是为了防止溢出
        int mid = lo + (hi - lo) / 2;

        if (a[mid] == target) {
            return mid;     // 找到了，返回下标
        } else if (a[mid] < target) {
            lo = mid + 1;   // 中间值太小，目标在右半边
        } else {
            hi = mid - 1;   // 中间值太大，目标在左半边
        }
    }

    return -1;  // 搜索区间为空，说明没找到
}

int main() {
    vector<int> arr = {1, 3, 5, 7, 9, 11, 13, 15};

    cout << binarySearch(arr, 7) << endl;   // 输出: 3（找到，下标3）
    cout << binarySearch(arr, 11) << endl;  // 输出: 5（找到，下标5）
    cout << binarySearch(arr, 10) << endl;  // 输出: -1（没找到）
    cout << binarySearch(arr, 1) << endl;   // 输出: 0（找到，下标0）
    cout << binarySearch(arr, 15) << endl;  // 输出: 7（找到，下标7）

    return 0;
}

#include <iostream>
using namespace std;

// 题目：猜一个 1~100 之间的数字，系统告诉你"大了"或"小了"
// 每次二分缩小范围，最快猜到答案

// 假设答案是 secret = 73
int secret = 73;

// 模拟系统返回的比较结果
// 返回 -1 表示猜小了，0 表示猜中了，1 表示猜大了
int guess(int mid) {
    if (mid == secret) return 0;   // 猜中了
    if (mid < secret) return -1;   // 猜小了
    return 1;                       // 猜大了
}

int main() {
    int lo = 1, hi = 100;   // 搜索范围：1 到 100
    int attempts = 0;        // 记录猜测次数

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;  // 取中间值
        attempts++;

        int result = guess(mid);

        if (result == 0) {
            cout << "在第 " << attempts << " 次猜中了: " << mid << endl;
            break;
        } else if (result == -1) {
            cout << "第 " << attempts << " 次猜了 " << mid << " → 小了" << endl;
            lo = mid + 1;   // 答案在右半边
        } else {
            cout << "第 " << attempts << " 次猜了 " << mid << " → 大了" << endl;
            hi = mid - 1;   // 答案在左半边
        }
    }
    // 输出：
    // 第 1 次猜了 50 → 小了
    // 第 2 次猜了 75 → 大了
    // 第 3 次猜了 62 → 小了
    // 第 4 次猜了 68 → 小了
    // 第 5 次猜了 71 → 小了
    // 第 6 次猜了 73 → 猜中了: 73
    // 只用了 6 次就从 1~100 中找到了！

    return 0;
}