说到算法,很多人可能一开始接触到的算法就是二分查找法,这种算法思想容易理解,使用场景也比较多。下面我会分享一些与平时不一样的二分查找法的实现形式:
首先我们先来看一下二分查找法的性能:
在没有对这种算法进行优化的情况下,它的时间复杂度和空间复杂度如下:
时间复杂度:
- 最坏情况:$O(logn)$
- 最好情况:如果查找的元素恰好在数组中央,那么就只需要执行一次,则为$O(1)$
空间复杂度:
- 需要常数个指针 $ i, j, m$,因此额外占用的空间是 $O(1)$
所以我这里主要是根据时间复杂度来研究二分查找法,下面我会列出二分查找法的几种的版本:
1、二分查找法基础版:
1 | // 二分查找法基础版 |
这是最基础的二分查找法,方法有两个参数,一个是查找的数组,一个是目标值;在这种写法里面,我定义的是一种左右区间都闭合的做法,数组的低值和高值都作为比较对象(使用二分查找法默认数组已排序),算法思路就是通过低位和高位的索引的和算出数组长度中间值的索引mid
,然后通过这个索引来找到这个数来与目标值做对比,如果目标值在数组的左边,那么中间值索引及右边的数都不用继续查找了,这时高位的索引等于中间值的索引 -1,然后再继续循环;如果目标值在数组的右边,那么数组左边的数就不用计算了,那么就可以得出低位的索引等于中间值的索引 +1,然后继续循环;最后如果中间值的索引指向的这个数与目标值相等,那么就是找到了,直接返回索引即可。若找到低位与高位的索引都重叠了,还是没找到的话,那么就是数组中没有这个数,直接返回 -1表示没找到。
这个版本有几个细节问题需要注意,如下:
(1)、为什么需要low <= height,而不是low < height ?
因为当这个目标数处在首位(或者一直找到最后一位才是目标数值的时候)的时候,需要判断到首位这个数本身才能查找到,如果判断条件没有等于,就等于少了这次判断,会导致无法查到而返回false(-1)。
(2)、为什么 “ mid = (high + low) / 2 ” 这个代码本身会存在bug?
如果这个数组的长度是整数类型的最大值,那么高位high = 2147483647 - 1,如果这个时候,目标数值在中间值的右边时,低位就会变成low = 1073741823 + 1;此时再去计算中间值 mid = -536870913,这就会引发错误。出现这种问题的原因是再次计算中间值索引的时候,低位和高位值相加,已经超出了整数的取值范围,导致这个数变成了负数。正常来说,计算出来的值是3221225470,但是实际计算出来的值是-1073741826;而JVM的底层保存数值是通过补码的形式来进行存储的,把这两个数的补码拿出来做对比就很明显了:
1 | 3221225470,它的补码是:1011 1111 1111 1111 1111 1111 1111 1110 |
Java的数值是带符号位的,首位的符号位“ 1 ”表示负数,所以等值再次取出来的时候就变成了-1073741826,而负数的除2还是负数,这就是问题的关键。
要解决这个问题也简单,那么就是使用无符号的右移1位来代替除2,在计算机基础中,有介绍到,一个二进制数的右移1位等于这个数除以2;左移一位则表示乘以2。而且这种写法也可以适用其他的语言。
1 | mid = (high + low) >>> 1; |
(3)、为什么代码里面比较符号都是用的小于号,有什么好处吗?
因为比较符合阅读的观感,能在一定程度上增强阅读效果。
所以修改过后的代码如下:
1 | // 二分查找法改动版 |
这里需要注意的是,” >>> “是无符号右移。
2、二分查找法改动版:
这种方法是从基础版的基础上改进的,采用的是左闭右开的范围查找,高位的值不作为查找的目标,当最后一个低值不相等的时候,就表示数组里面没有查找的数。
1 | // 二分查找法改动版 |
在这种方法中,低值可以作为搜索值,但是高位值不作为搜索值(边界),循环判断条件是小于高位,那么当判断到最后两个数值的时候,如果是大于中间值的话,low = high,这时判断不成立,就会返回-1。
这里的循环判断条件不要加上等于,否则会死循环!!比如,传入的目标数是处于数组值的中间位置且这个数不存在时,那么等到目标值查找到最后两个数的时候,就会发现这两个数都不是且大于中间值,然后low+high相加右移1,发现mid的值还是low,然后循环判断条件还是满足的,就会一直循环下去。
3、二分查找法平衡版:
这种方法采用的也是左闭右开的范围查找,判断依据是如果这个目标值是小于中间值的时候,高位索引就等于mid
;而等于或者小于的情况,低位索引就等于mid
,因为最后low = mid,而这里只是查找low
索引,后面判断一次就可以了。下面是方法实现:
1 | // 二分查找法平衡版 |
low
指向的可能是目标,而high
指向的不是目标,目标值不在循环内找出,等到范围内只剩low
的时候退出循环,在循环外判断low
指向的值与目标值是否相等,循环内的平均比较次数较少了,时间复杂度是$Θ(log(n))$。
这种算法的优缺点就是,如果是最好的情况时间复杂度会变大($O(1)$的时候,mid
就是目标值,但是执行变多了),如果是最坏的情况就变小了(判断变少了)。
后面再分享两种特殊的二分查找法:最左优先法和最右优先法。
4、二分查找法最左优先法:
前面的方法里面,如果给定的数组内有重复数据,没有要求返回的值必须遵循最左或最右的值的话,那么上面的算法是没问题的,如果有类似的需求,那么就不能用上面的方法来左了。
下面我会介绍一个最左优先法的版本,顾名思义就是返回数组里面有重复目标值的最左索引,下面是代码实现:
1 | // 二分查找法最左优先法:匹配最左边相同的值 |
遇到匹配的数值先不返回,而是标记为候选者,当查找到最左边的那个目标值的时候,候选者才是最终索引;如果查找不到的话,返回的就是候选者对象初始的值,即 -1。
5、二分查找法最左优先法改良版:
这种方法有点类似 Java中Arrays类里面的二分查找法,这种方法是如果在没有查找到目标值的时候,就返回一个大于或等于最靠做的索引位置。
1 | /** |
在这种方法里面,如果目标值有多个,就会返回正确的最左索引位置;如果不存在,就会返回比目标值大的最左索引位置,这个位置为插入位置。可以利用这种方法来求排名、前任。
6、二分查找法最右优先法:
这种方法的实现思路与最左优先法相似,只是返回的是目标值的最右边的索引位置。下面是代码实现:
1 | // 二分查找法最右优先法:匹配最右边相同的值 |
逻辑思路与最左匹配法相似,这里就不多赘述了。
7、二分查找法最右优先法改良版:
1 | /** |
在这种方法里面,如果目标值有多个,就会返回正确的最右边的索引位置;如果不存在,就会返回比目标值大的最右索引位置,这个位置为插入位置。可以利用这种方法来求排名、后任。
当然,二分查找法还有其他的实现形式,比如递归实现、迭代实现和分治实现,这些实现形式日后再做分享。
本文链接: https://longzas.github.io/2023/10/04/%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE%E6%B3%95/
版权声明: 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处!