证明，对于[lo, mid]和[mid,hi]两个区间，至少有一边是sorted的：
- pivot在mid时，pivot右边都是sorted的，所以[mid,hi]一定是sorted的
- pivot在[lo, mid)，pivot右边都是sorted的，所以[mid,hi]一定是sorted的
- pivot在(mid, hi]，pivot左边都是sorted的，所以[lo,mid]一定是sorted的
所以我们每次判断的时候，能一定能判断半边是sorted的，如果target在这个区间里，去这个区间找。否则去另外一个区间。
代码如下：
也可以在判断的时候顺便判断target是不是在lo或者hi，找的的话直接return。不过这样做也不会对时间有多大的影响，个人更习惯第一种写法。代码如下：
No comments:
Post a Comment