经典题目——二分查找

二分查找

引例：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个升序的数组旋转之后的数组，输出数组中最小的元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。数组可能包含重复项。数组内所含元素非负，若数组大小为0，请返回-1。

---

查找类问题最优解一定是O(logN)级的，首选二分法。只不过本题的二分有些奇怪。在课堂上讲的二分的使用条件必须是单调的，但在OJ的世界中将该理论推广：
$对于函数f(x) x\in (x_{1},x_{2})，只要f(x1) \neq f(x2)$对于函数f(x)x∈(x1​,x2​)，只要f(x1)​=f(x2)均可以使用二分法。换言之，只要首尾不相等，就可以使用二分，只不过一次只能找出一个符合要求的元素。

下面回到引例，题目给出的旋转数组其值走势是这样的：

正如我们给出的二分法的使用条件，要想使用二分法，必须要将后端（黑色部分）的值干掉。原因很简单，试想这么一个图，黑色部分无限延伸，mid = (left+right) >> 1 之后mid还是位于黑色线段上，按照二分算法，下一步会一分为二，选择右半边，这样与我们所求的点越来越远，最终收敛到一个错误的答案。

class Solution {
public:
    int findMin(vector<int>& nums) {
        int n = nums.size() - 1;
        if(n < 0)return -1;
        while(n >= 0 && nums[n] == nums[0])n--;
        if(nums[n] > nums[0])return nums[0];//说明剩余的部分是递增的
        int left = 0,right = n;
        while(left < right){//划分区间为[0,mid], [mid+1,right]
            int mid = left + right >>1;
            if(nums[mid] < nums[0]){
                right = mid;
            }else{
                left = mid + 1;
            }
        }
        return nums[right];
    }
};