每周一算法之二分查找(Kotlin描述)

2019-04-04 本文已影响3人熊喵先森

algorithms.png

简述: 从这篇文章起就会开启另一个系列就是上篇文章中提到的每周学习一个基本算法，会结合LeetCode上题目来做分析。解题的语言一般是Kotlin或Java. 如果涉及到一些有关Kotlin的知识点也会做一些介绍。如果平时就养成学习数据结构算法以及刷题的习惯，不管今后你是面试(愿从此再也不是面试造火箭平时拧螺丝了)或在实际上工作中都会对你有很大帮助。这也是这个系列文章的目的。

一、时间复杂度

最坏时间复杂度 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下标值。

四、算法过程演示

image

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

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

1、 循环递推实现方式
image
2、递归实现方式
image

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

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

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

1、出现问题的原因

我们可以确定 low 和 high 都是非负数，那么也就是二进制表示的最高位符号位是0，并且low 和 high 都是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的值就变成了负数 -1073741824，low = mid + 1, low就变成负数了。然后target的值会一直比mid要大 low就不断累加，直到low又累加到1073741824，mid 又变成 -1073741824，不断往复进入了死循环导致超时。可以看下面这个例子:

image

运算结果:

image

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

一起来看下例子:

image

运行结果:

image

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

1、Java中的 >>> 与 >> (或Kotlin中的 ushr 与 shr ) 的区别

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

2、Kotlin中的位运算

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

image

八、LeetCode上二分查找相关的题目(练一练)

注意: 在做二分查找题目之前，给几点建议。

1、真正在做题过程很少会有直接写标准的二分查找的题目，一般都是需要变型，转化成二分查找的问题。所以掌握二分查找思想比掌握实现方式更重要。

2、一般是二分查找去解题有个很明显的特征那就是 升序数组或有序数组，以及在一些查找数中对时间复杂度要求比较高，比如时间复杂度必须低于O(n), 很明显你不能直接用循环去做，二分查找的平均时间复杂度是O(log n) 明显低于 O(n), 可能就需要你考虑是否能用二分查找。

3、还有一个典型使用二分查找的题目，就是求平方根或者求完全平方数，有个通用结论是: 一个非负数n的平方根小于n/2 + 1。所以就转化了从[0,n/2 + 1]查找符合的平方根或完全平方数。