Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
Your algorithm's runtime complexity must be in the order of O(log n).
Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
題目
假設(shè)有一個(gè)升序排列的數(shù)組譬圣，但是隨機(jī)的旋轉(zhuǎn)了幾位，具體旋轉(zhuǎn)了多少不知道在辆，現(xiàn)在讓我們找到數(shù)組中的特定元素蔫骂，返回索引值队他。要求時(shí)間復(fù)雜度為 O(log n)
思路
數(shù)組本身有序徒役，但是旋轉(zhuǎn)以后，就變成了局部有序于游。時(shí)間復(fù)雜度要求 O(log n)毁葱，即要是用二分法。所以問題就二分后怎么選取下一步區(qū)間的問題贰剥。
首先數(shù)組一分為二倾剿，獲取mid，無論數(shù)組怎么旋轉(zhuǎn)蚌成，肯定有半邊是有序的前痘。
所以判斷一下nums[mid]和nums[0]的大小，
- 如果nums[mid]>=nums[0]担忧，說明數(shù)組左邊是升序的芹缔，再以此為前提，繼續(xù)判斷：
- nums[0]<=target<nums[mid]：則在[0,mid-1]里找;
- 否則在[mid+1,len-1]里找瓶盛。
- 如果nums[mid]<nums[0]最欠，說明數(shù)組右邊是升序的，再以此為前提惩猫，繼續(xù)判斷：
- nums[len]>=target>nums[mid]：則在[mid+1,len-1]里找;
- 否則在[0,mid-1]里找
最后注意一下邊界條件：mid可能會(huì)等于0窒所，target也可能等于每一次縮小范圍的邊界上的數(shù)，所以可以加以判斷帆锋，減少計(jì)算
代碼
int len=nums.length;
int l=0;
int r=len-1;
while (l<=r) {
int mid=(l+r)/2;
if (nums[mid]==target) {
return mid;
}
if (nums[mid]>=nums[0]) {//左半邊是遞增的
if (target==nums[l]) {
return l;
}
if (nums[mid]>target&&target>nums[0]) {//在左邊找
r=mid-1;
}else {
l=mid+1;//在右邊找
}
}else {//右半邊是遞增的
if (target==nums[r]) {
return r;
}
if (nums[mid]<target&&target<nums[len-1]) {
l=mid+1;
}else {
r=mid-1;
}
}
}
return -1;
