LeetCode短视频 | 以后要求时间复杂度log的一定就是二分算法了

• 2019 年 12 月 23 日
• 筆記

接下来继续做二分查找的算法，看下面图片，我们第4题号已经做完了，参考这里。

然后我看了第29题，好像有点难，暂时就不做了。接着就做下面一道『搜索旋转排序数组』。

题目：

而对于我们要找的target，target不在的那一段，所有数字可以看做无穷大，这样整个数组就可以看做有序的了，可以用正常的二分法去找 target 了，例如：

[ 4 5 6 7 1 2 3] ，如果 target = 5，那么数组可以看做 [ 4 5 6 7 inf infinf ]。

[ 4 5 6 7 1 2 3] ，如果 target = 2，那么数组可以看做 [ -inf -inf – inf -inf 1 2 3]。

和解法一一样，我们每次只关心 mid 的值，所以 mid 要么就是 nums [ mid ]，要么就是 inf 或者 -inf。

什么时候是nums [ mid ] 呢？

当nums [ mid ] 和 target 在同一段里边。

怎么判断nums [ mid ] 和 target 在同一段？

把nums [ mid ] 和 target 同时与 nums [ 0 ] 比较，如果它俩都大于 nums [ 0 ] 或者都小于 nums [ 0 ]，那么就代表它俩在同一段。例如

[ 4 5 6 7 1 2 3]，如果 target = 5，此时数组看做 [ 4 5 6 7 inf infinf ]。nums [ mid ] = 7，target > nums [ 0 ]，nums [ mid ] > nums [ 0 ]，所以它们在同一段 nums [ mid ] = 7，不用变化。

怎么判断nums [ mid ] 和 target 不在同一段？

把nums [ mid ] 和 target 同时与 nums [ 0 ] 比较，如果它俩一个大于 nums [ 0 ] 一个小于 nums [ 0 ]，那么就代表它俩不在同一段。例如

[ 4 5 6 7 1 2 3]，如果 target = 2，此时数组看做 [ – inf – inf – inf – inf 1 2 3]。nums [ mid ] = 7，target < nums [ 0 ]，nums [ mid ] > nums [ 0 ]，一个大于，一个小于，所以它们不在同一段 nums [ mid ] = – inf，变成了负无穷大。

执行过程贴视频，请欣赏！

贴代码

——END——