⚠️ This visualization was AI-generated and may contain inaccuracies. Please verify against the original LeetCode problem (#33) before relying on it.
Home → Algorithms → Search in Rotated Sorted Array

🔍 Search in Rotated Sorted Array

An interactive visualization of modified binary search on a rotated sorted array. Watch the algorithm determine which half is sorted and narrow down the search space step by step.

Binary Search LeetCode 33 ↗ Medium

The Problem

There is an integer array nums sorted in ascending order (with distinct values), which is possibly rotated at an unknown pivot index k.

For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 to become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not.

You must write an algorithm with O(log n) runtime complexity.

Interactive Visualization

Speed:
Array
Current Step
Press Step or Play to begin.
Code
fun search(nums: IntArray, target: Int): Int {    var lo = 0; var hi = nums.size - 1    while (lo <= hi) {        val mid = (lo + hi) / 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}

How It Works

Key Insight

In a rotated sorted array, when you split it at any midpoint, at least one half is always sorted. This is the crucial observation that lets us apply binary search even though the whole array is not sorted. We can check which half is sorted, determine if the target lies within that sorted half, and eliminate half the search space each step.

The Algorithm

  • Initialize: lo = 0, hi = len(nums) - 1
  • Each iteration: compute mid = (lo + hi) // 2
  • Check target: if nums[mid] == target, return mid
  • Left half sorted (nums[lo] <= nums[mid]): if target is in [nums[lo], nums[mid]), search left (hi = mid - 1); otherwise search right (lo = mid + 1)
  • Right half sorted: if target is in (nums[mid], nums[hi]], search right (lo = mid + 1); otherwise search left (hi = mid - 1)
  • If loop ends: target not found, return -1

Complexity

Time O(log n)
Space O(1)

Each iteration eliminates half of the remaining search space, giving us O(log n) time. Only a constant number of variables are used regardless of input size.