二分查找

二分查找

一、时间复杂度

最坏时间复杂度 O(log n)

最优时间复杂度 O(1)

平均时间复杂度 O(log n)

二、基本思想

在一个有序的列表中,要查找的数与列表中间的位置相比,若相等说明找到了,若要查找的数大于列表中间的数,说明要查找的数可能在有序列表的后半部分;若要查找的数小于列表中间的数,说明要查找的数可能在有序列表的前半部分;然后类似上述操作缩短查找范围,最后直到查找到最后一个数,如果不等于要查找的数,那么查找范围就为空。

三、算法步骤

给定一个包含n个带值的元素数组或序列A[0], … A[n-1],使A[0] <= … <= A[n-1],以及目标值Target.

  • 1、令 low = 0, high = n - 1

  • 2、若low > high, 则表示查找失败结束

  • 3、令mid(中间值元素)为 (low + high) / 2的值向下取整 (注意: 在具体实现中为了防止溢出,一般会采用 low + (high - low) / 2的值向下取整 或者直接采用位运算的移位运算来实现除2的操作。这个后面会有具体题目来说明)

  • 4、若Target > A[mid], 令 low = mid + 1 (说明要查找的值在序列或数组后半部分(除去自身),移动low游标,缩小查找范围),并回到步骤2

  • 5、如果Target < A[mid], 令 high = mid - 1 (说明要查找的值在序列或数组前半部分(除去自身),移动high游标,缩小查找范围),并回到步骤2

  • 6、如果Target == A[mid], 查找成功并结束,返回mid下标值。

  • 7、需要注意: 一定需要分析题目中二分查找那个目标值是否一定存在,如果确定一定存在,那么这个值一定是low和high相等时候找到的,所以while条件是 low < high而不是low <= high. 如果不确定存在,那么就是正常的low <= high.

四、算法过程演示

五、代码实现(Kotlin语言描述)

二分查找算法主要有两种实现方式,一种是循环递推的方式,另一种则是递归的方式

  • 1、 循环递推实现方式

  • 2、递归实现方式

六、为什么Java中mid = (low + high) / 2方式会溢出

相信刷过LeetCode题目的小伙伴们可能会在刷二分查找的题目过程会遇到超过时间限制的错误

不知道大家有没有去分析过为什么会得到超时啊,我都用了二分查找了时间复杂度都变成 O(log n) 呢,为啥还会超时呢。实际上是int数据类型溢出导致出现负数,使得代码进入了死循环,然后导致超时,最后OJ给你个超出时间错误。

  • 1、出现问题的原因

我们可以确定 lowhigh 都是非负数,那么也就是二进制表示的最高位符号位是0,并且lowhigh 都是31位二进制的整数

假设下面这种场景:


high = 0100 0000 0000 0000 0000 0000 0000 0000 = 1073741824 (Integer.MAX_VALUE的一半)

low = 0100 0000 0000 0000 0000 0000 0000 0000 = 1073741824 (Integer.MAX_VALUE的一半)

当执行 low + high 操作时,进行二进制运算,如下


high + low = 1000 0000 0000 0000 0000 0000 0000 0000

针对上述high + low 运算的结果,如果是无符号的32位(4个字节)Integer来说就表示 2147483648 (Integer.MAX_VALUE的大小);如果是有符号的32位(4个字节)Integer来说就表示 -2147483648。 需要特别注意的是Java或Kotlin中是不支持无符号的Integer类型,只存在有符号的Integer类型

所以问题就来了,如果是在Java或Kotlin中 (low + high) / 2的值就变成了负数 -1073741824low = mid + 1, low就变成负数了。然后target的值会一直比mid要大 low就不断累加,直到low又累加到1073741824mid 又变成 -1073741824,不断往复进入了死循环导致超时。可以看下面这个例子:

运算结果:

  • 2、解决该问题的方式

针对上述问题,你可能看到两种解决问题的办法,一种是采用 low + (high - low) / 2,另一种就是 (low + high) >>> 1 或 Kotlin中的 (low + high) ushr 1.


(high + low) >>> 1 = 0100 0000 0000 0000 0000 0000 0000 0000 = 1073741824

一起来看下例子:

运行结果:

七、补充一下Kotlin和Java中的位运算的知识点

  • 1、Java中的 >>>>> (或Kotlin中的 ushrshr ) 的区别

实际上无符号右移运算符>>>(或kotlin中的ushr)和右移运算符>>(或kotlin中的shr)是一样的,只不过右移时左边是补上符号位,而无符号右移运算符是补上0

  • 2、Kotlin中的位运算

在Kotlin中抛弃了Java那种直接使用 >>>、>>、<<、&、~、|、^这些非语义化的符号来实现位运算,说真的这样符号对代码可读性确实降低了很多,看过源码小伙伴就知道,很多源码中为了追求代码的运行效率,往往会采用位运算,但是代码理解和读起来就有点费力了。然而很高兴的是Kotlin却采用一种更加语义化的中缀调用函数(infix)来实现位运算,能够做到真正的简明识义, 并且用起来就像是在使用运算符一样,但是它更加具有含义。


   转载规则


《二分查找》 mikyou 采用 知识共享署名 4.0 国际许可协议 进行许可。
 上一篇
链表 链表
链表一、链表的定义链表是一种递归的数据结构,是一种线性结构,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针(Pointer),简单来说链表并不像数组那样将数组存储在一个连续的内存地址空间里,它们可以不是连续的因为他们
下一篇 
Java中ArrayList源码解析 Java中ArrayList源码解析
Java中ArrayList源码解析一、ArrayList介绍ArrayList是Java和Android开发中使用最为频繁的一种集合。它的底层数据结构是动态数组,并且是线程不安全,允许元素为null. ArrayList类结构如下: //
2020-01-02