Binary Search的变种。由于rotated的存在，直接A[mid]<key的判断并无法解决继续搜索哪一半边。
思路是分情况，分为左半边有序还是右半边有序，再细分是继续搜索左半侧还是右半侧。可以用开区间做也可以闭区间，个人习惯闭区间。
class Solution { public: int search(vector<int>& nums, int target) { int low=0, high=nums.size()-1; int mid; while (low<=high){ mid = (low+high)/2; if (nums[mid]==target) return mid; if (nums[0]<=nums[mid]){ //left side is in order if (nums[0]<=target && target<nums[mid]) high=mid-1; else low=mid+1; }else{ //right side is in order if (nums[mid]<target && target<=nums[high]) low=mid+1; else high=mid-1; } } return -1; } };
其中 nums[0]==nums[mid] 归到了 nums[0]<nums[mid]。 由于没有重复的元素，nums[0]==nums[mid] 只可能在搜索区间只有两个元素的时候出现。此时，如果左边元素就是target，之前的语句就会return，因此一定不是第一个元素，low=mid+1，因此可以归到 nums[0]<nums[mid] 中。二分的边界情况还是要小心。
LeetCode 33. Search in Rotated Sorted Array
原文：https://www.cnblogs.com/hankunyan/p/9123940.html