本文共 7226 字，大约阅读时间需要 24 分钟。

你不知道的事

你肯定听说过在有序数组中，通过二分算法查找等于指定的值？但是…

你是否听说过在有序数组中，通过二分算法查找大于等于指定的值的最左下标？

你是否听说过在有序数组中，通过二分算法查找小于等于指定的值的最右下标？

你是否听说过在无序数组中，也可以用二分算法？知道如何用二分算法解决局部最小值问题吗？

骚算法

package com.nobody.search;/** * @author Mr.nobody * @Description 二分查找 * @date 2020/9/5 */public class Code01_BinarySearch {
       // 二分查找，在有序数组中查找指定值，找到返回下标，否则返回-1    public static int binarySearch(int[] sortedArr, int num) {
           if (null == sortedArr || sortedArr.length == 0) {
               return -1;        }        int left = 0;        int right = sortedArr.length - 1;        int mid = 0;        while (left <= right) {
               // 等同于mid = (left + right) / 2;            // 但是下面的表达式既速度快，还能避免left+right溢出            mid = left + ((right - left) >> 1);            if (sortedArr[mid] == num) {
                   return mid;            } else if (sortedArr[mid] > num) {
                   right = mid - 1;            } else {
                   left = mid + 1;            }        }        return -1;    }    // 二分查找，在有序数组中查找大于等于指定值的最左的数，找到返回下标，否则返回-1    // 例如数组[1, 2, 2, 5, 8, 10, 11, 11, 11, 20]，指定值为2，则返回下标1    // 指定值为7，则返回下标为4；指定值为0，返回下标0；指定值为25，则返回下标-1    public static int greaterEqualBinarySearch(int[] sortedArr, int num) {
           if (null == sortedArr || sortedArr.length == 0) {
               return -1;        }        int left = 0;        int right = sortedArr.length - 1;        int mid = 0;        // 记录满足的最左下标        int mostLeftIndex = -1;        while (left <= right) {
               // 等同于mid = (left + right) / 2;            // 但是下面的表达式既速度快，还能避免left+right溢出            mid = left + ((right - left) >> 1);            if (sortedArr[mid] >= num) {
                   mostLeftIndex = mid;                right = mid - 1;            } else {
                   left = mid + 1;            }        }        return mostLeftIndex;    }    // 二分查找，在有序数组中查找小于等于指定值的最右的数，找到返回下标，否则返回-1    // 例如数组[1, 2, 2, 5, 8, 10, 11, 11, 11, 20]，指定值为2，则返回下标2    // 指定值为7，则返回下标为3；指定值为0，返回下标-1；指定值为25，则返回下标9    public static int lessEqualBinarySearch(int[] sortedArr, int num) {
           if (null == sortedArr || sortedArr.length == 0) {
               return -1;        }        int left = 0;        int right = sortedArr.length - 1;        int mid = 0;        // 记录满足的最右下标        int mostRightIndex = -1;        while (left <= right) {
               // 等同于mid = (left + right) / 2;            // 但是下面的表达式既速度快，还能避免left+right溢出            mid = left + ((right - left) >> 1);            if (sortedArr[mid] <= num) {
                   mostRightIndex = mid;                left = mid + 1;            } else {
                   right = mid - 1;            }        }        return mostRightIndex;    }    // 二分查找，在数组中(不一定要有序)查找局部最小数(随便一个就可以)，找到返回下标，否则返回-1    // 何为局部最小值，当某一个位置i的数，只要小于等于i-1和i+1位置的数时，即i位置的数就是局部最小值    // 如果不存在i-1或i+1位置，就不需要比较，例如0位置的数只需要小于等于1位置的数即可；    // n-1位置的数只需要小于等于n-2位置的数即可;    public static int localMinBinarySearch(int[] arr) {
           if (null == arr || arr.length == 0) {
               return -1;        }        if (arr.length == 1 || 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 mid = 0;        while (left <= right) {
               // 等同于mid = (left + right) / 2;            // 但是下面的表达式既速度快，还能避免left+right溢出            mid = left + ((right - left) >> 1);            if (arr[mid - 1] >= arr[mid] && arr[mid] <= arr[mid + 1]) {
                   // 既小于等于左边，又小于等于右边，满足局部最小值                return mid;            } else if (arr[mid - 1] < arr[mid]) {
                   // 大于左边，则左边是↘...↗走势，那肯定在左边区间一定存在局部最小值                right = mid - 1;            } else if (arr[mid] > arr[mid + 1]) {
                   // 大于右边，则右边是是↘...↗走势，那肯定在右边区间一定存在局部最小值                left = mid + 1;            }        }        return -1;    }}

测试

package com.nobody.search;import com.nobody.sort.Code01_InsertionSort;import java.util.Arrays;/** * @author Mr.nobody * @Description * @date 2020/9/6 */public class Main {
       public static void main(String[] args) {
           int[] arr = {
   1, 2, 2, 5, 8, 10, 11, 11, 11, 20};        int num = 2;        System.out.print("有序数组：");        Arrays.stream(arr).forEach(e -> System.out.print(e + " "));        System.out.println();        System.out.println("待查找数：" + num);        System.out.println("查找的下标：" + Code01_BinarySearch.binarySearch(arr, num));        System.out.println("----------------------------------------");        System.out.println("大于等于的数：" + 2 + "，最左下标为："                + Code01_BinarySearch.greaterEqualBinarySearch(arr, 2));        System.out.println("大于等于的数：" + 7 + "，最左下标为："                + Code01_BinarySearch.greaterEqualBinarySearch(arr, 7));        System.out.println("大于等于的数：" + 0 + "，最左下标为："                + Code01_BinarySearch.greaterEqualBinarySearch(arr, 0));        System.out.println("大于等于的数：" + 25 + "，最左下标为："                + Code01_BinarySearch.greaterEqualBinarySearch(arr, 25));        System.out.println("----------------------------------------");        System.out.println("小于等于的数：" + 2 + "，最右下标为："                + Code01_BinarySearch.lessEqualBinarySearch(arr, 2));        System.out.println("小于等于的数：" + 7 + "，最右下标为："                + Code01_BinarySearch.lessEqualBinarySearch(arr, 7));        System.out.println("小于等于的数：" + 0 + "，最右下标为："                + Code01_BinarySearch.lessEqualBinarySearch(arr, 0));        System.out.println("小于等于的数：" + 25 + "，最右下标为："                + Code01_BinarySearch.lessEqualBinarySearch(arr, 25));        System.out.println("----------------------------------------");        int[] arr1 = {
   1, 2, 2, 10, 8, 4, 2, 11, 7, 20};        System.out.print("数组：");        Arrays.stream(arr1).forEach(e -> System.out.print(e + " "));        System.out.println("，局部最小值下标：" + Code01_BinarySearch.localMinBinarySearch(arr1));        int[] arr2 = {
   4, 2, 2, 10, 8, 4, 2, 11, 7, 5};        System.out.print("数组：");        Arrays.stream(arr2).forEach(e -> System.out.print(e + " "));        System.out.println("，局部最小值下标：" + Code01_BinarySearch.localMinBinarySearch(arr2));        int[] arr3 = {
   7, 2, 2, 10, 8, 4, 2, 11, 7, 20};        System.out.print("数组：");        Arrays.stream(arr3).forEach(e -> System.out.print(e + " "));        System.out.println("，局部最小值下标：" + Code01_BinarySearch.localMinBinarySearch(arr3));        int[] arr4 = {
   3, 2, 4, 10, 8, 6, 7, 11, 7, 10};        System.out.print("数组：");        Arrays.stream(arr4).forEach(e -> System.out.print(e + " "));        System.out.println("，局部最小值下标：" + Code01_BinarySearch.localMinBinarySearch(arr4));    }}

测试结果

有序数组：1 2 2 5 8 10 11 11 11 20 待查找数：2查找的下标：1----------------------------------------大于等于的数：2，最左下标为：1大于等于的数：7，最左下标为：4大于等于的数：0，最左下标为：0大于等于的数：25，最左下标为：-1----------------------------------------小于等于的数：2，最右下标为：2小于等于的数：7，最右下标为：3小于等于的数：0，最右下标为：-1小于等于的数：25，最右下标为：9----------------------------------------数组：1 2 2 10 8 4 2 11 7 20 ，局部最小值下标：0数组：4 2 2 10 8 4 2 11 7 5 ，局部最小值下标：9数组：7 2 2 10 8 4 2 11 7 20 ，局部最小值下标：6数组：3 2 4 10 8 6 7 11 7 10 ，局部最小值下标：5

转载地址：https://javalib.blog.csdn.net/article/details/108428294 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！