Coding problem · Medium · Binary Search

Search in Rotated Sorted Array

Medium Algorithms & data structures Most askedSeen at Meta, Amazon, Microsoft, LinkedIn

An ascending array of distinct integers was rotated at an unknown pivot (e.g. [0,1,2,4,5,6,7] → [4,5,6,7,0,1,2]). Given the rotated array nums and a target, return its index or -1, in O(log n).

Example 1

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

Example 2

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

Constraints

All values are distinct

Hints

Hint 1

At any mid, at least one half — [lo, mid] or [mid, hi] — is sorted.

Hint 2

Check whether the target lies inside the sorted half; if so search there, otherwise search the other half.

Write and run your solution

Loading the editor… (JavaScript is required to run code in your browser.)

Solution and explanation

Show the solution

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

Compare nums[lo] with nums[mid]: if nums[lo] <= nums[mid] the left half is sorted, so the target is there exactly when nums[lo] <= target < nums[mid]. Otherwise the right half is sorted and the same check applies to (nums[mid], nums[hi]]. Discard the other half each step.

Reference solution

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;
}

function search(nums: number[], target: number): number {
  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;
}

def search(nums: list[int], target: int) -> int:
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[lo] <= nums[mid]:
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        elif nums[mid] < target <= nums[hi]:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

<?php

function search(array $nums, int $target): int
{
    [$lo, $hi] = [0, count($nums) - 1];
    while ($lo <= $hi) {
        $mid = intdiv($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;
            }
        } elseif ($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;
    }
}

Binary Search · Easy