@[toc]
你不知道的事
你肯定听说过在有序数组中，通过二分算法查找等于指定的值？但是...
你是否听说过在有序数组中，通过二分算法查找大于等于指定的值的最左下标？你是否听说过在有序数组中，通过二分算法查找小于等于指定的值的最右下标？
你是否听说过在无序数组中，也可以用二分算法？知道如何用二分算法解决局部最小值问题吗？
骚算法
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
