33 & 81. Search in Rotated Sorted Array I & II

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){

1. if ( middle == target ), return
2. else if ( middle in [B,C] region)
   1. if target in [B, middle) region => right = middle – 1;
   2. else (target in (middle, B]) => left = middle + 1
3. else ( middle in [A, (B-1)] region)
   1. if (target in (middle , (B-1)] region) =>left = middle + 1;
   2. 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)