33. 搜索旋转排序数组

题目：

第一次思考：

1. 对于复杂度logn，想到二分查找
2. 但首先整个数组不是完全有序的，存在旋转
3. 目前思路是
   1. 通过二分查找找到旋转的位置
   2. 分别对旋转位置左右进行二分查找

实现：

class Solution {
public:int binarySearch(vector<int>& nums,int l,int r,int target){int ret=-1;while(l<=r){int mid=(l+r)/2;if (nums[mid]==target){ret=mid;break;}else if (nums[mid]<target){l=mid+1;}else{r=mid-1;}}return ret;}int search(vector<int>& nums, int target) {if (target==nums[0]) return 0;if (nums.size()<=1) return binarySearch(nums,0,nums.size()-1,target);int left=0;int right=nums.size()-1;while(left<right){int mid=(left+right)/2;if (nums[mid]<nums[left]){right=mid;}else if (nums[mid]>nums[left]){left=mid;}else{break;}}int rotate_pos=left==0?nums.size()-2:left;left=0;right=rotate_pos;bool find_=false;int ret=-1;left=1;right=rotate_pos;ret=binarySearch(nums,left,right,target);if (ret==-1){left=rotate_pos+1;right=nums.size()-1;ret=binarySearch(nums,left,right,target);}return ret;}
};