普通二分查找
/**
* 普通二分查找
*/
public class BinarySearch01 {
public static int search(int[] arr, int num) {
if (arr == null || arr.length == 0) return -1;
int l = 0;
int r = arr.length - 1;
int mid;
while (l <= r) {
mid = l + ((r - l) >> 1);
if (arr[mid] > num) r = mid - 1;
else if (arr[mid] < num) l = mid + 1;
else return mid;
}
return -1;
}
}
在有序数组中查找大于等于某个数的最左侧位置
二分法不仅可以用于寻找某个指定的值，还可以寻找每个值出现的最左或最右位置，但是这种二分就不是寻找到指定的值就返回，而是继续二分，直到二分尽为止
/**
* 二分查找大于等于某个数的最左侧位置
* 如：数组 000111222333，num 1
* 则返回的下标为3
*/
public class BinarySearch02 {
public static int search(int[] arr, int num) {
if (arr == null || arr.length == 0) return -1;
int l = 0;
int r = arr.length - 1;
int index = -1;
while (l <= r) {
int mid = l + ((r - l) >> 1);
if (arr[mid] >= num) {
index = mid; // arr[mid]是目前已知的大于等于num的最左侧位置
r = mid - 1; // 排查mid右边的数
} else l = mid + 1; // mid以及mid左边的数都比num小，排查mid以及mid左边的数
}
return index;
}
}
在有序数组中查找小于等于某个数的最右侧位置
/**
* 二分查找小于等于某个数的最右侧位置
* 如：数组 000111222333，num 5
* 则返回的下标为3
*/
public class BinarySearch03 {
public static int search(int[] arr, int num) {
if (arr == null || arr.length == 0) return -1;
int l = 0;
int r = arr.length - 1;
int index = -1;
while (l <= r) {
int mid = l + ((r - l) >> 1);
if (arr[mid] > num) r = mid - 1; //mid以及mid右侧都是大于num的数，都排除
else {
index = mid; // 目前已知的小于等于num的最右侧位置
l = mid + 1; // 排除左边的数
}
}
return index;
}
}
寻找局部最小
不一定是有序的数组才能二分，只要找到一种规律，可以一次排除掉一半的数据，就可以做二分
/**
* 寻找局部最小
* arr数组无序，并且相邻两个数不相等，从中找出一个局部最小的数，并返回下标
* 局部最小：
* 比如下标为i的数，如果小于小标i-1和i+1的数，则下标为i的数就是局部最小
* 如果下标为0的数，小于下标为1的数，则下标为0的数就是局部最小
* 如果下标为arr.length-1的数，小于arr.length-2的数，则arr.length-1的数就是局部最小
*/
public class BinarySearch04 {
public static int search(int[] arr) {
if (arr == null || arr.length == 0) return -1;
if (arr.length == 1) return 0;
//arr[0] < arr[1]，所以arr[0]满足局部最小，返回0
if (arr[0] < arr[1]) return 0;
//arr[arr.length - 1] < arr[arr.length - 2]，所以arr[arr.length - 1]满足局部最小，返回arr.length - 1
if (arr[arr.length - 1] < arr[arr.length - 2]) return arr.length - 1;
//此时l~r范围内，arr[l] > arr[l+1] 趋势递减，arr[arr.length-2] < arr[arr.length-1]趋势递增
//中间必有最小值
int l = 1;
int r = arr.length - 2;
while (l <= r) {
int mid = l + ((r - l) >> 1);
//找到局部最小，返回
if (arr[mid] < arr[mid - 1] && arr[mid] < arr[mid + 1]) return mid;
//如果arr[mid] > arr[mid - 1]，则arr[mid-1] < arr[mid]，趋势递增，l~mid中间必有最小值
//r赋值为mid-1
else if (arr[mid] > arr[mid - 1]) r = mid - 1;
//arr[mid]小于arr[mid-1]，只能排除左边的一部分，从右边的一部分寻找局部最小
else l = mid + 1;
}
return -1;
}
}