如何写出正确的二分法以及分析

二分法在平时经常用到,除了查找某个key的下标以外,还有很多变形的形式。比如 STL 里的 lower_bound,upper_bound

总结一下注意点,有这么几个:

  • 数组是非递增还是非递减
  • 结束条件,即while (condition) 应当是<还是<=
  • 求mid应当是偏向左还是右,即 mid = (left + right) » 1, 还是 mid = (left + right + 1) » 1
  • 如何得到循环不变式
  • while结束后是否需要判断一次条件

整理了下常见的几个问题如下:

  1. 查找值key的下标,如果不存在返回-1.
  2. 查找值key第一次出现的下标x,如果不存在返回-1.
  3. 查找值key最后一次出现的下标x,如果不存在返回-1.
  4. 查找刚好小于key的元素下标x,如果不存在返回-1.
  5. 查找刚好大于key的元素下标x,如果不存在返回-1,等价于std::upper_bound.
  6. 查找第一个>=key的下标,如果不存在返回-1,等价于std::lower_bound.

leetcode上也有很多类似的题目。例如:Search a 2D Matrix

二分查找,必须条件是有序数组,然后不断折半,几乎每次循环都可以降低一半左右的数据量。因此是O(lgN)的方法,要注意的是二分查找要能够退出,不能陷入死循环。

二分查找用到的一个重要定义就是循环不变式,顾名思义,就是在循环中不会改变这么一个性质。举个例子,插入排序,不断的循环到新的索引,但保持前面的排序性质不变。其实就是数学归纳法,具体的定义不用管,我们在第一个例子里看下。

1. 查找值为key的下标,如果不存在返回-1.

先看一下伪代码:

这里面包含怎样的循环不变式呢?

如果中间值比key大,那么[mid, right]的值我们都可以忽略掉了,这些值都比key要大。

只要在[left, mid-1]里查找就是了。相反,如果中间值比key小,那么[left, mid]的值可以 忽略掉,这些值都比key要小,只要在[mid+1, right]里查找就可以了。如果相等,表示找到了, 可以直接返回。因此,循环不变式就是在每次循环里,我们都可以保证要找的index在我们新构造 的区间里。如果最后这个区间没有,那么就确实是没有

注意mid的求法,可能会int越界,但我们先不用考虑这个问题,要记住的是这点:

mid是偏向left的,即如果left=1,right=2,则mid=1。

参考代码:

接着考虑一个复杂一点的问题

2. 查找值key第一次出现的下标x,如果不存在返回-1.

我们仍然考虑中间值与key的关系:

  1. 如果array[mid]<key,那么x一定在[mid+1, right]区间里。
  2. 如果array[mid]>key,那么x一定在[left, mid-1]区间里。
  3. 如果array[mid]≤key,那么不能推断任何关系。 比如对key=1,数组{0,1,1,2,3},{0,0,0,1,2},array[mid] = array[2] ≤ 1,但一个在左半区间,一个在右半区间。
  4. 如果array[mid]≥key,那么x一定在[left, mid]区间里。

综合上面的结果,我们可以采用1,4即<和≥的组合判断来实现我们的循环不变式,即循环过程中一直满足key在我们的区间里。

这里需要注意两个问题:

  1. 循环能否退出,我们注意到4的区间改变里是令right = mid,如果left=right=mid时,循环是无法退出的。 换句话说,第一个问题我们始终在减小着区间,而在这个问题里,某种情况下区间是不会减小的!
  2. 循环退出后的判断问题,再看下我们的条件1,4组合,只是使得我们最后的区间满足了≥key,是否=key,还需要再判断一次。

参考代码:

接下来的这个问题还有一个小小的坑,需要注意下:

3. 查找值key最后一次出现的下标x,如果不存在返回-1.

省去分析的过程,我们直接写下想到的循环不变式:

  1. 如果array[mid]>key,那么x一定在[left, mid-1]区间里。
  2. 如果array[mid]≤key, 那么x一定在[mid, right]区间里。

这里需要注意个问题:

在条件2里,实际上我们是令left=mid,但是如前面提到的,如果left=1,right=2,那么mid=left=1, 同时又进入到条件2,left=mid=1,即使我们在while设定了left < right仍然无法退出循环,解决的办法很简单: mid = (left + right + 1) >> 1 ,向右偏向就可以了。

参考代码:

接下来的题目都是类似的。

只贴下循环不变式和参考代码,如果你有别的心得,或者这篇文章有错误欢迎提出。

4. 查找刚好小于key的元素下标x,如果不存在返回-1.

  1. 如果array[mid]<key,那么x在区间[mid, right]
  2. 如果array[mid]≥key,那么x在区间[left, mid-1]

参考代码:

5. 查找刚好大于key的元素下标x,如果不存在返回-1,等价于std::upper_bound.

  1. 如果array[mid]>key,那么x在区间[left, mid]
  2. 如果array[mid]≤key,那么x在区间[mid + 1, right]

参考代码:

6. 查找第一个>=key的下标,如果不存在返回-1,等价于std::lower_bound.

  1. 如果array[mid]<key,那么x在区间[mid + 1, right]
  2. 如果array[mid]≥key,那么x在区间[left, mid]

参考代码:

如果有什么疑问或者错误,欢迎指出。

1 3 收藏 1 评论

关于作者:yingshin

简介还没来得及写 :) 个人主页 · 我的文章 · 3 ·  

相关文章

可能感兴趣的话题



直接登录
最新评论
跳到底部
返回顶部