Suppose a sorted array 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.
Analysis:
Transformed binary searching (BS).
Since it has been sorted but just rotated once, we need to make full use of the sorted feature.
Based on the binary search, we continue to use BS but in a little different way. Anyway, we need to drop half of the vector after each search.
See figure below for detailed implementation for how to drop half of vector after each searching.
There are two cases in this condition, so we need to identify each case first. After identifying the two cases, in each case, we need to further identify that we need to keep the left side or right side.
After those identification, finally we can keep one half of the vector in each searching, which is similar to the running time of BS, O(lgn).
////////////////////////////////////////////////////////////////////////////////
//code 4ms
class Solution {
public:
int search(vector<int>& nums, int target) {
int n = nums.size(), mid = n / 2;
int l = 0, r = n - 1;
while (l <= r){
if (target<nums[mid]){
//case 1
if (nums[l] <= nums[mid]){
if (target >= nums[l]){//left side
r
= mid - 1;
mid
= (l + r) / 2;
}
else{//right
side
l
= mid + 1;
mid
= (l + r) / 2;
}
}
//case 2
else{//left
side
r
= mid - 1;
mid
= (l + r) / 2;
}
}
else if (target>nums[mid]){
//case 2
if (nums[r] >= nums[mid]){
if (nums[r] >= target){//right
side
l
= mid + 1;
mid
= (l + r) / 2;
}
else{//left
side
r
= mid - 1;
mid
= (l + r) / 2;
}
}
//case 1
else {//right
side
l
= mid + 1;
mid
= (l + r) / 2;
}
}
else return mid;
}
return -1;
}
};
No comments:
Post a Comment