左神讲算法——二分法及其拓展

古城微笑少年丶 2022-10-06 15:57 234阅读 0赞

### 目录 ###

*  1. 经典二分例题
 *  2. 拓展例题一：寻找大于等于某数最左侧位置
 *  3. 拓展例题二：局部最小值问题

> **参考链接**：[2021最新左神数据结构算法全家桶][2021]

--------------------

# 1. 经典二分例题 #

题目一：在一个有序数组中，找到某个数是否存在

1️⃣ 如果采用暴力法，时间复杂度为`O(N)`

public static int findNum(int[] arr, int num) { 
        for (int i = 0; i < arr.length; i++) { 
            if (arr[i] == num)
                return i;
        }
        return -1;
    }

2️⃣ 可以采用二分法，时间复杂度为`O(log2N)`（可以理解为每次砍一半，需要砍几次，例如N=8，需要砍三次到1）

public static int binaryFindNum(int[] arr, int left, int right, int num) { 
        if (left > right)//递归结束
            return -1;
        int mid = (left + right) / 2;
        int midVal = arr[mid];
        if (num > midVal)
            return binaryFindNum(arr, mid + 1, right, num);//向右递归
        else if (num < midVal)
            return binaryFindNum(arr, left, mid - 1, num);//向左递归
        else
            return mid;
    }

--------------------

# 2. 拓展例题一：寻找大于等于某数最左侧位置 #

题目：在一个有序数组中，找大于等于某数最左侧的位置

该题目仍然可以用二分法来解决，由于数组有序，首先判断数组的中间数是否大于指定数，如果大于等于则继续在右半边寻找，如果小于则从左半边寻找；然后在半边部分继续使用二分，直到无法二分为止，所找到的位置就是所求位置。如下图案例所示：  
![image-20210614193218367][]  
代码如下：

public static int binary(int[] arr, int left, int right, int num) { 
        if (left > right)//递归结束
            return -1;
        int mid = (left + right) / 2;
        int midVal = arr[mid];
        //如果当前中间值>=num且左边元素也>=num,则向左递归
        if (mid - 1 >= 0 && midVal >= num && arr[mid - 1] >= num)
            return binary(arr, left, mid - 1, num);//向左递归
        //如果当前中间值>=num但左边元素<num,则直接返回该中间值
        else if (mid - 1 >= 0 && midVal >= num && arr[mid - 1] < num)
            return mid;
        //其他情况向右递归
        else
            return binary(arr, mid + 1, right, num);//向右递归
    }

由此可见，不仅仅是找一个数存不存在可以用二分，找>=某数最左侧位置或者<=某数最右侧位置都可以用二分

--------------------

# 3. 拓展例题二：局部最小值问题 #

题目：在一个无序数组中，任何两个相邻的数不相等，求一个局部最小的位置，规定时间复杂度小于`O(N)`

> 局部最小的定义如下：
> 
>  *  对于0位置即数组的第一个元素，如果该数小于1位置的数，则0位置为局部最小位置
>  *  对于n-1位置即数组最后一个元素，如果该数小于n-2位置的数，则n位置为局部最小位置
>  *  对于数组中间i元素，如果它小于i-1位置的数同时也小于i+1位置的数，则i位置为局部最小位置

**思路**：首先判断0位置是不是局部最小，是则直接返回；然后判断1位置是不是局部最小，是则直接返回；如果0位置和1位置都不是局部最小，该情况如下图所示，则中间元素必然存在局部最小，分析如下：  
![image-20210614195452398][]  
0位置>1位置，所以0指向1箭头向下，n-2位置<n-1位置，所以n-1指向n-2箭头向下。由于数组中两两元素不相等，所以每相邻两元素间都有如图所示的箭头，而由于进是一个向下的方向，出是一个向上的方向，因此中间必然存在一个低谷，即局部最小  
![image-20210614195925534][]  
那怎么找到局部最小的位置呢？我们同样可以用**二分**来解决，首先取数组中间元素M，如果M为局部最小，则直接返回，否则假设M>M-1的位置，则M到M-1为一个向下的箭头。则按照上面的分析，由于0位置和M-1位置的方向相反，则\`\`0M-1\`区间必然存在局部最小，则我们继续在\`0M-1\`区间二分，依次类推，不断二分直到中间位置为局部最小返回即可  
![image-20210614200404898][]  
代码如下：

public static int binaryMin(int[] arr, int left, int right) { 
        //判断0位置是不是局部最小
        if (arr[0] < arr[1])
            return 0;
        //判断arr.length-1位置是不是局部最小
        if (arr[arr.length - 2] > arr[arr.length - 1])
            return arr.length - 1;
        if (left > right)//递归结束
            return -1;
        int mid = (left + right) / 2;
        int midVal = arr[mid];
        //如果二分中点是局部最小
        if (mid - 1 >= 0 && mid + 1 <= arr.length - 1 && midVal < arr[mid - 1] && midVal < arr[mid + 1])
            return mid;
        //如果二分中点大于等于左边元素,向左递归
        else if (mid - 1 >= 0 && mid + 1 <= arr.length - 1 && midVal >= arr[mid - 1])
            return binaryMin(arr, left, mid - 1);
        //向右递归
        else
            return binaryMin(arr, mid + 1, right);
    }

由此可见，不是只有数组有序才能二分，无序也可以，取决于特殊的问题和数据状况

[2021]: https://www.bilibili.com/video/BV1Vb4y1f7kK?p=2&t=5533
[image-20210614193218367]: /images/20221005/a35bdfcd5ddd472fa3b071e2fc09a733.png
[image-20210614195452398]: /images/20221005/d5a3c5ba70ac49b28a8459e0ef1ff337.png
[image-20210614195925534]: /images/20221005/2496fcad903a4dca852cf99491433f33.png
[image-20210614200404898]: /images/20221005/cf433c195993466d9300a1d3ffa52a77.png