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 7might become4 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);
}