我是陈皮，一个在互联网 Coding 的 ITer，微信搜索「陈皮的JavaLib」第一时间阅读最新文章，回复【资料】，即可获得我精心整理的技术资料，电子书籍，一线大厂面试资料和优秀简历模板。

你不知道的事

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

• 你是否听说过在有序数组中，通过二分算法查找大于等于指定的值的最左下标？
• 你是否听说过在有序数组中，通过二分算法查找小于等于指定的值的最右下标？
• 你是否听说过在无序数组中，也可以用二分算法？知道如何用二分算法解决局部最小值问题吗？

骚算法

package com.nobody.search;

/**
 * @author 陈皮
 * @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