題目鏈接
tag:
- Medium辛慰；
- Binary Search深员；
question：
??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
Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
思路：
??這道題讓在旋轉(zhuǎn)數(shù)組中搜索一個給定值负蠕，若存在返回坐標，若不存在返回-1倦畅。我們還是考慮二分搜索法遮糖，但是這道題的難點在于我們不知道原數(shù)組在哪旋轉(zhuǎn)了，我們還是用題目中給的例子來分析叠赐，對于數(shù)組[0 1 2 4 5 6 7] 共有下列七種旋轉(zhuǎn)方法：
0 1 2 4 5 6 7
7 0 1 2 4 5 6
6 7 0 1 2 4 5
5 6 7 0 1 2 4
4 5 6 7 0 1 2
2 4 5 6 7 0 1
1 2 4 5 6 7 0
??二分搜索法的關(guān)鍵在于獲得了中間數(shù)后欲账，判斷下面要搜索左半段還是右半段，我們觀察上面紅色的數(shù)字都是升序的芭概，由此我們可以觀察出規(guī)律赛不，如果中間的數(shù)小于最右邊的數(shù)，則右半段是有序的罢洲，若中間數(shù)大于最右邊數(shù)踢故，則左半段是有序的，我們只要在有序的半段里用首尾兩個數(shù)組來判斷目標值是否在這一區(qū)域內(nèi)惹苗，這樣就可以確定保留哪半邊了殿较，代碼如下：
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
else if (nums[mid] < nums[right]) {
if (nums[mid] < target && nums[right] >= target) left = mid + 1;
else right = mid - 1;
} else {
if (nums[left] <= target && nums[mid] > target) right = mid - 1;
else left = mid + 1;
}
}
return -1;
}
};
