Search in Rotated Sorted Array

MediumBinary Search

A sorted array of distinct values was rotated at an unknown pivot. Return the index of a target value, or -1 if it is absent, in O(log n).

Open problem

Constraints

1 <= nums.length <= 5000
All values are distinct
-10^4 <= target <= 10^4

Binary search with sorted-half check

Time O(log n)Space O(1)

At each step one half around mid is sorted. Decide which half is sorted by comparing endpoints, then check whether the target lies inside that sorted half to choose which side to keep searching.

#include <bits/stdc++.h>
using namespace std;

int search(vector<int>& nums, int target) {
    int lo = 0, hi = nums.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] == target) return mid;
        if (nums[lo] <= nums[mid]) { // left half sorted
            if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
            else lo = mid + 1;
        } else { // right half sorted
            if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
            else hi = mid - 1;
        }
    }
    return -1;
}