二分查找(蓝桥杯备赛)

1、寻找峰值

（1）题目描述

峰值元素是指其值严格大于左右相邻值的元素。给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。你可以假设 nums[-1] = nums[n] = -∞。

你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

（2）解题思路

题目已知最最左边和最右边都是深渊，我们比较nums[mid]和nums[mid+1]：

如果nums[mid] > nums[mid+1]，则当前为下坡，那么mid或者mid左边一定有一座山峰。

如果nums[mid] < nums[mid+1]，那么当前为上坡，那么mid右边一定有一座山峰。

如果nums[mid] = nums[mid+1]，那么当前为平地，又”峰值严格大于左右相邻值”，所以这一定不是山峰，那么其左边或右边一定有一座山峰。（这种情况先不讨论，比较复杂）

这道题目的单调性比较抽象，认真思考一下。

(3)代码

int findPeakElement(int* nums, int numsSize) {

    int left = 0;

    int right = numsSize - 1;

    while (left < right) {

        int mid = left + (right - left) / 2;

        if (nums[mid] > nums[mid+1]) right = mid;

        if (nums[mid] < nums[mid+1]) left = mid + 1;

    }

    return left;

}

2、有序矩阵中第 K 小的元素

（1）题目描述

给你一个 n x n 矩阵 matrix，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。请注意，它是排序后的第 k 小元素，而不是第 k 个不同的元素。你必须找到一个内存复杂度优于 O(n²) 的解决方案。

（2）解题思路

• 不断枚举 mid，左边界是 matrix[0][0]，右边界是 matrix[n-1][n-1]
• 当数组中 <= mid 的个数 >= k：high = mid
• 当个数 < k：low = mid + 1
• 范围不断合理缩小，只有当 low == high 就是答案
• 时间复杂度：O(n * log(high – low))
• 单调性：数越小，比他小的越少

（3）代码

// 辅助函数：统计矩阵中 <= mid 的元素个数
int check(int** matrix, int n, int mid) {
    int count = 0;
    int r = n - 1;
    int c = 0;

    while (r >= 0 && c < n) {
        if (matrix[r][c] <= mid) {
            count += (r + 1);
            c++;
        } else {
            r--;
        }
    }
    return count;
}

int kthSmallest(int** matrix, int matrixSize, int* matrixColSize, int k) {
    int n = matrixSize;
    int low = matrix[0][0];
    int high = matrix[n - 1][n - 1];

    while (low < high) {
        int mid = low + (high - low) / 2;

        if (check(matrix, n, mid) >= k) {
            high = mid; // 可能mid就是答案
        } else {
            low = mid + 1; // mid一定不是答案
        }
    }

    return low;
}