Search in Rotated Sorted Array

medium binary search rotated array

Problem

There is an integer array nums sorted in ascending order (with distinct values). Prior to being passed to your function, nums is rotated at an unknown pivot index k (0 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]. For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Inputnums = [4,5,6,7,0,1,2], target = 0

Output4

At each mid, exactly one half is still sorted. Check whether target lies in that sorted half — if yes, recurse there; otherwise the other half.

nums (comma-separated)

target

def search(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target: return mid
        if nums[lo] <= nums[mid]:        # left half sorted
            if nums[lo] <= target < nums[mid]: hi = mid - 1
            else: lo = mid + 1
        else:                             # right half sorted
            if nums[mid] < target <= nums[hi]: lo = mid + 1
            else: hi = mid - 1
    return -1

function search(nums, target) {
  let lo = 0, hi = nums.length - 1;
  while (lo <= hi) {
    const mid = (lo + hi) >> 1;
    if (nums[mid] === target) return mid;
    if (nums[lo] <= nums[mid]) {
      if (nums[lo] <= target && target < nums[mid]) hi = mid - 1; else lo = mid + 1;
    } else {
      if (nums[mid] < target && target <= nums[hi]) lo = mid + 1; else hi = mid - 1;
    }
  }
  return -1;
}

class Solution {
    public int search(int[] nums, int target) {
        int lo = 0, hi = nums.length - 1;
        while (lo <= hi) {
            int mid = (lo + hi) >>> 1;
            if (nums[mid] == target) return mid;
            if (nums[lo] <= nums[mid]) {
                if (nums[lo] <= target && target < nums[mid]) hi = mid - 1; else lo = mid + 1;
            } else {
                if (nums[mid] < target && target <= nums[hi]) lo = mid + 1; else hi = mid - 1;
            }
        }
        return -1;
    }
}

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

Explanation

The array was sorted, then rotated at some unknown pivot, so it is not fully sorted anymore. Even so, we can still find the target in O(log n) by leaning on one reliable fact: at every mid, one half is always still sorted.

At each step we compare nums[lo] with nums[mid]. If nums[lo] <= nums[mid], the left half is sorted; otherwise the right half is sorted. Knowing which side is in clean order lets us reason precisely about where the target can be.

If the sorted half's range actually contains the target, we search there; otherwise the target must be in the other half. For a sorted left half we check nums[lo] <= target < nums[mid] and move hi = mid - 1 if so, else lo = mid + 1. The right-half case mirrors this.

Example: nums = [4,5,6,7,0,1,2], target 0. First mid is 7; the left half [4..7] is sorted but 0 is not in it, so we go right. The window narrows into the [0,1,2] region and finds 0 at index 4.

Each step still discards half the elements, so the rotation costs us nothing in speed — we keep the full log n efficiency of binary search.

Time: O(log n) Space: O(1)