# 二分查找算法
# 目录
# 问题描述
从一个有序的数组中查找目标值,找到返回对应索引找不到则返回-1
# 二分查找基础版
/**
* 二分查找基础版
*
* @param a 待查找的数组
* @param target 待查找的目标值
* @return 找的目标值返回索引则找不到返回-1
*/
public static int binarySearchBasic(int[] a, int target) {
//1. 设置左指针和右指针的初值
int l = 0, r = a.length - 1;
while (l <= r) // 当左右指针中间范围有元素时执行
{
//获取中间值的索引, 使用逻辑右移(>>>), 而不是算术右移(>>)
int m = (l + r) >>> 1;
//比较
if (target < a[m]) {
r = m - 1; // 目标值在中间值左边
} else if (a[m] < target) {
l = m + 1; // 目标值在中间值右边
} else {
return m; //中间值等于目标值, 返回中间值索引
}
}
return -1; //循环内没有找到目标值
}
# 三个问题
# 为什么循环条件是 <= 而不是 < ?
因为 < 会漏掉一次判断, 当 左指针或者右指针指向的值是目标值时, 如果当 l == r 时不进行判断, 就会导致没有查找到这个元素
# 为什么不使用 /2 来获取左指针和右指针的 中间索引?
使用/2 会存在问题, 如果当 待搜索数组的大小约等于 int的最大值的一半时, 如果目标值在中间索引的右边,两个指针索引相加,这会产生一个负数,因为最高位变为了1,然而 int,long类型是有符号数字类型, 最高位如果为1 就是负数,当负数 /2 时. 得到的结果依然是一个负数, 导致索引报错等问题
解决方法 : 当负数 /2 时. 得到的结果依然是一个负数, 我们可以通过将数值进行 逻辑右移, 最高位补零,这样就可以使数值变为正常值
# 用自己的话描述算法
- 设置两个指针,分别指向数组的两端.
- 计算出两个指针索引的中间值
- 拿出中间值与目标值进行比较,假设是一个升序的数组
- 如果大于中间值,说明目标值可能出现在中间值右边, 则左指针的指向就要跳到中间值的下一个值, 即左指针+1,而右指针保持不变.
- 如果是小于中间值,那么说明目标值在中间值的左边,则右指针指向中间值的前一个值,即右指针-1.
- 如果中间值等于目标值,相当于我们找到了目标值,此时返回 中间值对应的索引即可
- 重复 2,3 这两个步骤,直到 左指针大于了右指针,此时说明没有找到目标值,返回-1. 再次之前,最后一次比较机会是, 左指针等于右指针,此时他俩指向的就是中间值,如果中间值相等就是左指针或者右指针对应的索引,否则返回-1
# 二分查找的改动版本
一共有三处改动
- 将右指针的含义进行改变, 从有可能指向目标值以及作为右边界,变为了 只是右边界,没有可能是目标值, 也就是左闭右闭,变成左闭右开区间
- 为了配合这个右指针的改变, 循环条件变为 l < r, l是有可能指向目标值的,而右指针不可能指向目标值, 所以他俩不相等,如果可以相等会出现死循环的bug
- 当中间值大于了目标值时, 说明中间值不可能是目标值, 则 r 的指针从原来的 m-1 变为了 m, 因为m-1是有可能为目标值的
代码
public static int binarySearchAlternative(int[] a, int target) {
int l = 0, r = a.length; //第一处改动
while (l < r) //第三处改动
{
int m = (l + r) >>> 1;
if (target < a[m]) {
r = m; //第三处改动
} else if (a[m] < target) {
l = m + 1;
} else {
return m;
}
}
return -1;
}
# java Arrays类提供的二分查找
在java 的java.util.Arrays 类中,提供了二分查找,其算法如下:
// Like public version, but without range checks.
private static int binarySearch0(byte[] a, int fromIndex, int toIndex,
byte key) {
int low = fromIndex;
int high = toIndex - 1;
while (low <= high) {
int mid = (low + high) >>> 1;
byte midVal = a[mid];
if (midVal < key)
low = mid + 1;
else if (midVal > key)
high = mid - 1;
else
return mid; // key found
}
return -(low + 1); // key not found.
}
三个参数分别是: 待查找数组,查找起始索引,查找目标 通过分析这个算法,发现除了最终的返回值与我们的二分查找算法的基础版不同,其他都相同.
- 因此也会出现"不平衡",既向左查找时,比较次数比向右查找次数多, 因为每次循环需要多比较一次.
为什么返回值是 -(low + 1)?
通过阅读方法上的注释说明(这里没复制),可以得知当查找的目标值不在数组中时, 返回的是有序数组插入的位置,既按照这个位置插入依然有序. 这个插入位置就是变量low的值,为什么要加个负号呢? 因为算法的返回结果是非负数时,表示找到了目标值,则返回负数是为了进行区分, 那么为什么low要 -1呢(-low -1), 这是因为如果 low值为0时, -0和0的值是相等的(补码,0只有一种),如果不减1的话,就会以为0索引为待查找目标,所以减1错开1位
# 最左查找和最右查找
当数组中含有相同的元素时,我们的需求是返回,最左或者最右的那个目标值的索引
最左查找
/**
* 二分查找最左版本, 当数组中含有重复元素时, 要求返回最靠左边的,即第一个目标元素的索引
*
* @param a 搜索数组
* @param target 待查找目标值
* @return <p>
* 找到返回索引,找不到返回-1
*/
public static int binarySearchLeftMost(int[] a, int target) {
int l = 0, r = a.length - 1;
//候补,将找到的目标值赋值给候补,直到找到更加靠左的目标值将其更新
int alternate = -1;
while (l <= r) {
int m = (l + r) >>> 1;
//比较
if (target < a[m]) {
r = m - 1;
} else if (a[m] < target) {
l = m + 1;
} else {
//找到目标值,更新候补
alternate = m;
//最左查找,更新右边界
r = m - 1;
}
}
return alternate; //循环内没有找到目标值
}
最右查找
/**
* 二分查找最右版本, 当数组中含有重复元素时, 要求返回最靠右边边的,即最后一个目标元素的索引
*
* @param a 搜索数组
* @param target 待查找目标值
* @return <p>
* 找到返回索引,找不到返回-1
*/
public static int binarySearchRightMost(int[] a, int target) {
int l = 0, r = a.length - 1;
//候补,将找到的目标值赋值给候补,直到找到更加靠左的目标值将其更新
int alternate = -1;
while (l <= r) {
int m = (l + r) >>> 1;
//比较
if (target < a[m]) {
r = m - 1;
} else if (a[m] < target) {
l = m + 1;
} else {
//找到目标值,更新候补
alternate = m;
//最左查找,更新右边界
l = m + 1;
}
}
return alternate; //循环内没有找到目标值
}
# 最左查找和最右查找变形算法
查找大于等于目标值的最左元素的索引
/**
* 最左二分查找变形.
*
* @param a 搜索数组
* @param target 待查找目标值
* @return <p>
* 返回值的含义是: 最靠左的大于等于目标元素的元素的索引
* <p>例子: int[] a = {1,2,4,4,4,6,7},
* <p>查找4, 返回索引2
* <p>查找3, 返回索引2
*/
public static int binarySearchLeftMost2(int[] a, int target) {
int l = 0, r = a.length - 1;
while (l <= r) {
int m = (l + r) >>> 1;
if (target <= a[m]) {
r = m - 1;
} else {
l = m + 1;
}
}
return l;
}
查找小于等于目标值的最右元素的索引
/**
* 最右二分查找变形.
*
* @param a 搜索数组
* @param target 待查找目标值
* @return <p>
* 返回值的含义是: 最靠右的小于等于目标元素的元素的索引
*/
public static int binarySearchRightMost2(int[] a, int target) {
int l = 0, r = a.length - 1;
while (l <= r) {
int m = (l + r) >>> 1;
if (target >= a[m]) {
l = m + 1;
} else {
r = m - 1;
}
}
return l - 1;
}
# 最左和最右变形算法应用
计算最近邻居,前任和后任的索引
计算范围的元素
