Description:
I. https://leetcode.com/problems/search-in-rotated-sorted-array/#/description
II. https://leetcode.com/problems/search-in-rotated-sorted-array-ii/#/description
Algorithm:
|B ————————————— C | A —————————— (B – 1) |
C is the largest number, A is the minimum number.
Squeeze from left and right.
while (left <= right){
- if ( middle == target ), return
- else if ( middle in [B,C] region)
- if target in [B, middle) region => right = middle – 1;
- else (target in (middle, B]) => left = middle + 1
- else ( middle in [A, (B-1)] region)
- if (target in (middle , (B-1)] region) =>left = middle + 1;
- else (target in [B, middle) region) => right = middle – 1;
}
if left > right => return -1 (cannot find target)
Code:
class Solution {
public:
int search(vector<int>& nums, int target) {
if (nums.empty()) return -1;
// nums.erase(unique(nums.begin(), nums.end()), nums.end()); // if II, use this function
int i = 0;
int n = nums.size();
int mid;
int high = n – 1;
while (i <= high) {
mid = (high + i) / 2;
if (nums[mid] == target) return mid;
if (nums[mid] < nums[high]) {
if (target > nums[mid] && nums[high] >= target) {
i = mid + 1;
}
else {
high = mid – 1;
}
}
else {
if (target >= nums[i] && nums[mid]>target) {
high = mid – 1;
}
else {
i = mid + 1;
}
}
}
return -1;
}
};
Time Complexity:
O(logn)