33 Search in Rotated Sorted Array

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.
Complexity: O(logN) time, O(logN) space
The Idea: Use binary search to find index of pivot, which we can identify as the minimum element in the array. In other words, the target value will have a unique position where both its left and right neighbors are the same or larger. Then use binary search to search left or right of pivot.
// no need to exit condition because we are guarentee to
// linearly converge to a pivot point (check is made that it exists)
int find_pivot(vector<int> &nums, int low, int high) {
int mid = low + ((high - low) / 2);
if (nums.at(mid) > nums.at(mid + 1)) {
return mid + 1;
}
else if (nums.at(low) <= nums.at(mid)) return find_pivot(nums, mid + 1, high);
else return find_pivot(nums, low, mid - 1);
}
int binary_search(vector<int> &nums, int low, int high, int target) {
if (high < low) return -1;
int mid = low + ((high - low) / 2);
if (nums.at(mid) == target) return mid;
else if (nums.at(mid) > target) return binary_search(nums, low, mid - 1, target);
else return binary_search(nums, mid + 1, high, target);
}
int search(vector<int>& nums, int target) {
if (nums.empty()) return -1;
int start = 0;
int end = nums.size() - 1;
// not rotated
if (nums.front() <= nums.back())
return binary_search(nums, start, end, target);
// find pivot point
int pivot_i = find_pivot(nums, start, end);
if (nums.at(pivot_i) == target)
return pivot_i;
// search right [pivot, end]
else if (target >= nums.at(pivot_i) && target <= nums.back())
return binary_search(nums, pivot_i + 1, end, target);
// search left [start, pivot]
else return binary_search(nums, start, pivot_i - 1, target);
}
Testing
int main()
{
// t1
vector<int> nums1 = { 1 };
assert(search(nums1, 1) == 0);
assert(search(nums1, -1) == -1);
// t2
vector<int> nums2 = { 4, 5, 6, 7, 0, 1, 2 };
for (int i = 0; i < nums2.size(); i++)
assert(search(nums2, nums2.at(i)) == i);
assert(search(nums2, 10) == -1);
// t3
vector<int> nums3 = { 4, 5, 1, 2, 3 };
for (int i = 0; i < nums3.size(); i++)
assert(search(nums3, nums3.at(i)) == i);
}