二分法：有序与特殊无序场景

二分法概述

二分法（Binary Search）就是每次把问题的范围缩小一半，直到找到答案或者确定答案不存在。

它常用在有序的数据里，比如从小到大排列的数字列表。

但有些特殊情况，能在无序的条件下使用二分法，要有二分的思想

假设我们有一个升序数组：

python

nums = [1, 3, 5, 7, 9, 11, 13]
target = 7

二分法的流程：

确定范围：left = 0，right = len(nums) - 1
取中间位置：mid = (left + right) // 2
比较：
- 如果 nums[mid] == target，找到了！
- 如果 nums[mid] < target，说明目标在右边 → left = mid + 1
- 如果 nums[mid] > target，说明目标在左边 → right = mid - 1
重复，直到找到或范围为空。

这样的时间复杂度是O(logn)，比遍历要好得多

有序数组中找到>=num最左的位置

给定一个有序数组和一个数字，找到大于等于该num的数字，这个数字是在最左侧的，也就是说再往左都小于num

我们可以用二分轻松解决这个问题，首先左右双指针分别指向数组头和尾，这是我们的寻找范围

找到左右指针中间（mid）的那一个数字，判断是否大于等于num：

如果大于等于num：说明mid右侧的数字全部都大于等于num，将右指针移动到mid - 1，抛弃所有右边继续判断
如果小于num：说明mid左侧的数字全都小于num，将左指针移动到mid + 1，抛弃所有左边继续判断

在判断的过程中，用一个变量reco记录符合条件的值，在往后的判断中如果还有左边的值符合则更新reco

我的代码：

java

    public static int findLeftIndex(int[] arr, int num) {
        // 用reco来记录当前找到的符合条件的值的索引, curMid来做二分
        // 两个指针left和right来缩小范围
        int reco = -1;
        int curMid = -1;
        int left = 0;
        int right = arr.length - 1;

        while (left <= right) {
            curMid = left + ((right - left) >> 1);
            if (arr[curMid] >= num) {
                reco = curMid;
                right = curMid - 1;
            } else {
                left = curMid + 1;
            }
        }
        return reco;
    }

！！注意：获取mid不用 (left + right) / 2是因为在数据量很大的时候，例如left = 10e, right = 18e时，left + right = 28e 会直接导致int类型值溢出！

因此我们采取用left加上right和left差值的一半的方法避免溢出，其中 >> 1是位运算，相当于/2，位运算的效率远高于四则运算

有序数组中找到<=num最右的位置

同上的思路可以类比写出二分法的代码：

java

    public static int findRightNum(int[] arr, int num) {

        int reco = -1;
        int curMid = -1;
        int left = 0;
        int right = arr.length - 1;

        while (left <= right) {
            curMid = left + ( (right - left) >> 1 );
            if (arr[curMid] <= num) {
                reco = curMid;
                left = curMid + 1;
            } else {
                right = curMid - 1;
            }
        }
        return reco;
    }

找到局部最小值

这是一个二分法用于无序数组中的经典案例

给定一个无序数组，长度为n，数组相邻两个数字不相等，请找到数组中的一个局部最小值

局部最小值：比左边的数小，比右边的数小

实现思路：局部最小值的实现可以借助函数导数的思路：

先对数组两端进行判断，若0位置的数小于1位置则是局部最小值，若n-1位置的数小于n-2位置也是局部最小值，这两个位置很特殊只用判断一个即可；若都不满足条件，则呈现以下规律：0-1单调递减，n-2到n-1单调递增，通过函数的知识不难知道，他们中间一定有局部最小值！也就是极小值
给定左右指针，对中间位置的数进行判断：
1. 如果mid位置的数满足比左右都小，则就是答案！
2. 如果mid位置的数大于左边一个数，mid-1到mid是单调递增的，那么在left和mid中间一定有局部最小值，此时将right = mid - 1即可
3. 如果mid位置的数大于右边一个数，mid到mid+1是单调递减的，那么在mid和right中间一定有局部最小值，此时将left = mid + 1即可
这样下去一定能找到局部最小值，这个值一定存在！

我的代码：

java

    public static int findBottomIndex(int[] arr) {
        // 处理边界
        if (arr.length == 1 || arr.length == 0) {
            return -1;
        }

        // 先对两边进行判断
        if (arr[0] < arr[1]) {
            return 0;
        }
        if (arr[arr.length - 1] < arr[arr.length - 2]) {
            return arr.length - 1;
        }

        // 处理核心
        int left = 0;
        int right = arr.length - 1;
        int rst = -1;
        
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (arr[mid] < arr[mid - 1] && arr[mid] < arr[mid + 1]) {
                rst = mid;
                break;
            } else if (arr[mid] > arr[mid - 1]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return rst;
    }