題目：
- 假設(shè)按照升序排序的數(shù)組在預(yù)先未知的某個(gè)點(diǎn)上進(jìn)行了旋轉(zhuǎn)。( 例如仿村，數(shù)組 [0,1,2,4,5,6,7] 可能變?yōu)?[4,5,6,7,0,1,2] )。搜索一個(gè)給定的目標(biāo)值兴喂，如果數(shù)組中存在這個(gè)目標(biāo)值蔼囊，則返回它的索引，否則返回 -1 衣迷。你可以假設(shè)數(shù)組中不存在重復(fù)的元素畏鼓。你的算法時(shí)間復(fù)雜度必須是 O(log n) 級別。
Example
輸入: nums = [4,5,6,7,0,1,2], target = 0
輸出: 4
思想：二分搜索法——對排好序的數(shù)組進(jìn)行二分查找壶谒！
兩步走：
- 先用二分法找到最大的數(shù),因?yàn)樽畲蟮臄?shù)左側(cè)為排好序的數(shù)云矫，因而用right來輔助，找到最大值的索引的代碼如下：
while(left<right-1){
int mid = (left+right)/2;
if (nums[mid]>nums[left]){
left = mid;
}
else {right = mid;}
}
int max = nums[left]>nums[right]? left:right;
- 找到最大數(shù)索引max后汗菜，原數(shù)組0-max, 與max - end-1 均為排好序的數(shù)組让禀，根據(jù)target選擇二分的數(shù)組即可：整體代碼如下：
class Solution {
public:
int search(vector<int>& nums, int target) {
if(!nums.size()) return -1;
if(nums.size()==1) return ((target==nums[0])-1);
int left=0,right=nums.size()-1;
while(left<right-1){
int mid = (left+right)/2;
if (nums[mid]>nums[left]){
left = mid;
}
else {right = mid;}
}
int max = nums[left]>nums[right]? left:right;
vector<int> nums2(nums.begin(),nums.begin()+max+1);
nums.erase(nums.begin(),nums.begin()+max+1);
if(target>=nums2[0]) return array_mid_serch(nums2,nums2.size(),target);
if(array_mid_serch(nums,nums.size(),target)>=0)
return array_mid_serch(nums,nums.size(),target)+max+1;
return -1;
}
private:
int array_mid_serch(vector<int>& arr,int lenth,int want_find)
{
int mid;
int left=0,right=lenth-1;
while(left<=right)
{
mid=(left+right)/2;
if(arr[mid]==want_find)
{
return mid;
}
else if(arr[mid]<want_find)
{
left=mid+1;
}
else
{
right=mid-1;
}
}
return -1;
}
};
其中private部分就是很經(jīng)典的二分搜索方法，可背一手陨界。附上雙百結(jié)果：
二分法搜索結(jié)果
