二分的题目，除了已经sorted的情况，只要有shift，肯定是一边sorted另一边非sorted的。那么二分的话有以下几种情况：
- 左边sorted，我们不确定应该去左边还是右边，因为有可能input数组就是sorted的
- 左边unsorted，hi = mid；左边unsorted我们是比较lo和mid的大小来确定的，mid的数小于lo的数，mid的数本身有可能是答案
- 右边sorted，hi = mid，无论左边是sorted还是unsorted，答案都是在左半边
- 右边unsorted，lo = mid + 1；因为mid的数大于hi的数，我们才能确定右边unsorted，那么mid的数本身一定不是答案
根据以上的分析我们可以知道判断右边是否sorted可以让代码更简洁，所以我们每次判断右边来二分，因为没有duplicated，所以时间复杂度是O(log n)，代码如下：
No comments:
Post a Comment