33. 搜索旋转排序数组

• 假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。

你可以假设数组中不存在重复的元素。

你的算法时间复杂度必须是 O(log n) 级别。

示例 1:

输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4
示例 2:

输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1

非常简单的题目，一看到复杂度是O(logn) ，又是查找元素的，直接就想到二分查找了。
二分查找无非就是lo,hi,mid。
那观察一下数组，很快就能发现规律，整个数组在某个点发生旋转，这意味着，数组仍然是"有序"的。
举个例子
输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4
我们可以看得出来 nums[mid]>nums[hi]的时候，说明旋转点在后面，换言之就是前面半段是完全有序的。后面半段会达到一个最高点，然后重新从最小值开始计数。
换个例子
nums = [6,7,0,1,2,4,5]
以这个数组为例子，当nums[mid]<nums[hi]的时候，就是代表后面半段是完全有序的。 是不会存在其他任何情况的，读者可以自行推导。
那么已知了这两种情况，那么我们就可以写题了，当出现这么两种情况，如果要求的值不在有序的半段中，就肯定在另外半段里了。
代码如下：

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int lo=0;
        int hi=nums.size()-1;
        if(hi<0) return -1;
        while(lo<hi){
            int mid=(hi-lo)/2+lo;
            if(nums[mid]==target){
                return mid;
            }
            if(nums[mid]>nums[hi]){
                if(target<nums[mid]&&target>=nums[lo]){
                    hi=mid-1;
                }
                else {
                    lo=mid+1;
                }
            }
            else if(nums[mid]<nums[hi]){
                if(target>nums[mid]&&target<=nums[hi]){
                    lo=mid+1;
                }
                else{
                    hi=mid-1;
                }
            }
        }
        
        if(hi>=0&&nums[hi]==target) return hi;
        return -1;
    }
};

值得注意的就是我的这个mid 是靠近lo的，因此退出循环只需要判断nums[hi]是否等于target即可。