力扣33、搜索旋转排序数组

1、二分法（4ms,69%;10.8MB,70%）

时间复杂度：O（log n）

空间复杂度：O（1）

 1 int search(vector<int>& nums, int target) {
 2         //这里的empty()注意是空则返回真
 3        if(nums.empty())
 4        return -1;
 5        if(nums.size()==1)
 6        return nums[0]==target? 0:-1;
 7        int left=0,right=nums.size()-1;
 8        int mid=0;
 9        while(left<=right){
10            mid=(left+right)/2;
11            if(nums[mid]==target)
12            return mid;
13            //这里的=是细节，当两者相等时是执行if而不是else
14            //if成立说明前半部分有序
15            if(nums[left]<=nums[mid]){
16                if(target>=nums[left]&&target<nums[mid])
17                right=mid-1;
18                else
19                left=mid+1;
20            }
21            //else成立说明后半部分有序
22            else{
23                if(target>nums[mid]&&target<=nums[right])
24                left=mid+1;
25                else
26                right=mid-1;
27            }
28        }
29        return -1;
30     }