经典应用场景与变式

3.1 二维矩阵中的二分查找

题目：搜索二维矩阵

题目描述：给你一个 m x n 的矩阵 matrix，其每行元素从左到右升序排列，且每行的第一个整数大于前一行的最后一个整数。请判断目标值 target 是否在矩阵中。

输入格式：

第一行：三个整数 m, n, target。
接下来 m 行，每行 n 个整数，表示矩阵。

输出格式：

如果存在输出 1，否则输出 0。

样例输入：

alt text

样例输出：

解题分析：

这种矩阵可以看作是一个“拉直”后的一维有序数组。
通过坐标映射：index = i * n + j，i = index / n，j = index % n。
然后直接对 [0, m*n - 1] 这个区间进行标准二分查找即可。

代码实现（ACM模式）：

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

int get(vector<vector<int>>& matrix, int index) {
    int n = matrix[0].size();
    int i = index / n;
    int j = index % n;
    return matrix[i][j];
}

bool searchMatrix(vector<vector<int>>& matrix, int target) {
    int m = matrix.size(), n = matrix[0].size();
    int left = 0, right = m * n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        int val = get(matrix, mid);
        if (val == target) return true;
        else if (val < target) left = mid + 1;
        else right = mid - 1;
    }
    return false;
}

int main() {
    int m, n, target;
    cin >> m >> n >> target;
    vector<vector<int>> matrix(m, vector<int>(n));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cin >> matrix[i][j];
        }
    }
    cout << (searchMatrix(matrix, target) ? 1 : 0) << endl;
    return 0;
}

3.2 寻找峰值

题目描述：峰值元素是指其值严格大于左右相邻值的元素。给你一个整数数组 nums，找到任意一个峰值元素并返回其索引。你可以假设 nums[-1] = nums[n] = -∞。

输入格式：

第一行：一个整数 N，表示数组长度。
第二行：N 个整数，表示数组元素。

输出格式：

一个整数，表示任意一个峰值的索引。

样例输入：

4
1 2 3 1

样例输出：

解题分析：

题目不要求数组有序，但要求 O(log N) 解法，暗示使用二分。
核心思想：比较 nums[mid] 和 nums[mid+1]。
- 如果 nums[mid] > nums[mid+1]，说明 mid 本身就是峰值或其左侧有峰值，收缩右边界 right = mid。
- 如果 nums[mid] < nums[mid+1]，说明峰值在 mid 右侧，收缩左边界 left = mid + 1。

代码实现（ACM模式）：

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

int findPeakElement(vector<int>& nums) {
    int left = 0, right = nums.size() - 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] > nums[mid + 1]) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

int main() {
    int N;
    cin >> N;
    vector<int> nums(N);
    for (int i = 0; i < N; i++) {
        cin >> nums[i];
    }
    cout << findPeakElement(nums) << endl;
    return 0;
}

3.3 搜索旋转排序数组

题目描述：一个升序排列的数组在某个未知点进行了旋转（例如，[0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2]）。给定一个目标值 target，如果在数组中则返回其索引，否则返回 -1。假设数组元素互不相同。

输入格式：

第一行：两个整数 N 和 target。
第二行：N 个整数，表示旋转后的数组。

输出格式：

一个整数，表示 target 的索引，若不存在则输出 -1。

样例输入：

7 0
4 5 6 7 0 1 2

样例输出：

解题分析：

旋转后的数组虽然整体无序，但从中点分割后，至少有一半是有序的。
我们可以判断 target 是否在有序的那一半里，从而决定收缩左边界还是右边界。

代码实现（ACM模式）：

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

int search(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) return mid;

        // 判断左半部分是否有序
        if (nums[left] <= nums[mid]) {
            // 左半部分有序
            if (target >= nums[left] && target < nums[mid]) {
                right = mid - 1; // target 在左半部分
            } else {
                left = mid + 1; // target 在右半部分
            }
        } else {
            // 右半部分有序
            if (target > nums[mid] && target <= nums[right]) {
                left = mid + 1; // target 在右半部分
            } else {
                right = mid - 1; // target 在左半部分
            }
        }
    }
    return -1;
}

int main() {
    int N, target;
    cin >> N >> target;
    vector<int> nums(N);
    for (int i = 0; i < N; i++) {
        cin >> nums[i];
    }
    cout << search(nums, target) << endl;
    return 0;
}

总结

要点	描述
核心思想	通过单调性，每次排除一半的搜索区间，达到 O(log N) 的效率。
模板选择	查找一个数用标准模板；查找最左/最右边界用左右边界模板。
泛化应用	先抽象出单调函数 `f(x)` 和自变量 `x`，再对 `x` 进行二分搜索。
常见陷阱	循环条件、边界更新、整数溢出、搜索区间是否为空。
竞赛技巧	在旋转数组、山脉数组、二维矩阵等特殊结构上灵活应用二分思想。

*学习笔记

暂没有学习笔记，快来抢first blood ！

3.1 二维矩阵中的二分查找​

题目：搜索二维矩阵​

3.2 寻找峰值​

3.3 搜索旋转排序数组​

总结​

*学习笔记​

3.1 二维矩阵中的二分查找

题目：搜索二维矩阵

3.2 寻找峰值

3.3 搜索旋转排序数组

总结

*学习笔记