算法——二分法

基本介绍

二分法是 每次都排除半个区间，然后在剩余的半个区间内寻找解 的方法，排除半个区间的前提是：区间是有序的，这样一来，当解 小于 区间中点时，就可以在 左子区间 寻找；当解 大于 区间中点时，就可以在 右子区间 寻找。当解 等于 区间中点时，根据要求在子区间寻找或返回。

实现

二分法有两种实现：一种是找 前驱，一种是找 后继。在解决实际问题时需要根据问题的要求不同来采取不同的实现。

后继

定义

在单调递增序列中找 $x$ 或 $x$ 的后继 的定义：在单调递增序列 a 中，如果有 $x$，则找第一个 $x$ 的位置；如果没有 $x$，则找比 $x$ 大的 第一个数 的位置。

举例

例如对于 a = [1, 2, 4, 4, 6]，如果要找 $4$ 或 $4$ 的后继，则返回 第一个$4$ 的索引 2；如果要找 $3$ 或 $3$ 的后继，则返回比 $3$ 大的 第一个数（即第一个$4$）的索引 2。

代码

int binarySearch(int[] nums, int target) {
    int left = 0, right = nums.length - 1; // left, right 分别是区间的左端点和右端点
    while (left < right) {
        int mid = left + (right - left >> 1);
        if (target <= nums[mid]) { // 如果目标值小于或等于区间中点
            right = mid; // 则在左子区间查找
        } else { // 如果目标值大于区间中点
            left = mid + 1; // 则在右子区间查找
        }
    }
    return left; // 返回 第一个target的位置 或 第一个比target大的元素的位置
}

前驱

定义

在单调递增序列中找 $x$ 或 $x$ 的前驱 的定义：在单调递增序列 a 中，如果有 $x$，则找最后一个 $x$ 的位置；如果没有 $x$，则找比 $x$ 小的 最后一个数 的位置。

举例

例如对于 a = [1, 2, 4, 4, 6]，如果要找 $4$ 或 $4$ 的前驱，则返回 最后一个$4$ 的索引 3；如果要找 $5$ 或 $5$ 的前驱，则返回比 $5$ 小的 最后一个数（即最后一个$4$）的索引 3。

代码

int binarySearch(int[] nums, int target) {
    int left = 0, right = nums.length - 1; // left, right 分别是区间的左端点和右端点
    while (left < right) {
        int mid = left + (right - left + 1 >> 1);
        if (target < nums[mid]) { // 如果目标值小于区间中点
            right = mid - 1; // 则在左子区间查找
        } else { // 如果目标值大于或等于区间中点
            left = mid; // 则在右子区间查找
        }
    }
    return left; // 返回 最后一个target的位置 或 最后一个比target小的元素的位置
}