Search in Rotated Sorted Array

Problem

You are given an array of length n which was originally sorted in ascending order. It has now been rotated between 1 and n times. For example, the array nums = [1,2,3,4,5,6] might become:

• [3,4,5,6,1,2] if it was rotated 4 times.
• [1,2,3,4,5,6] if it was rotated 6 times.

Given the rotated sorted array nums and an integer target, return the index of target within nums, or -1 if it is not present.

You may assume all elements in the sorted rotated array nums are unique,

A solution that runs in O(n) time is trivial, can you write an algorithm that runs in O(log n) time?

Examples

Example 1:

Input: nums = [3,4,5,6,1,2], target = 1

Output: 4

Example 2:

Input: nums = [3,5,6,0,1,2], target = 4

Output: -1

Constraints

• 1 <= nums.length <= 1000
• -1000 <= nums[i] <= 1000
• -1000 <= target <= 1000
• All values of nums are unique.
• nums is an ascending array that is possibly rotated.

You should aim for a solution with O(logn) time and O(1) space, where n is the size of the input array.

Solution

We maintain a search window [l, r) using exclusive rhs indexing. The midpoint is the target check. If the left window element is less than or equal to midpoint, then the left subarray [l, m] is sorted. Otherwise the right subarray is sorted. For the respective sorted subarray, if the target falls within the sorted window range, then search that sub-window. Otherwise search the other side.

Essentially, we can only make inferences based on the sorted sub array, so check against that always, and on false we check the other side.

class Solution {
public:
    int search(vector<int>& nums, int target) {
        std::size_t l = 0;
        std::size_t r = nums.size(); // search interval is [l, r)
 
        while (l < r) {
            const std::size_t m = std::midpoint(l, r);
 
            if (nums[m] == target) {
                return static_cast<int>(m);
            }
 
            // Left side [l, m] is sorted.
            if (nums[l] <= nums[m]) {
                if (nums[l] <= target && target < nums[m]) {
                    r = m;       // keep [l, m)
                } else {
                    l = m + 1;   // keep [m + 1, r)
                }
            }
            // Right side [m, r) is sorted.
            else {
                if (nums[m] < target && target <= nums[r - 1]) {
                    l = m + 1;   // keep [m + 1, r)
                } else {
                    r = m;       // keep [l, m)
                }
            }
        }
 
        return -1;
    }
};