13  Search in a Rotated Sorted Array

Rank 11 · Pattern: modified binary search · Target: \(O(\log n)\) time, \(O(1)\) space

13.1 Problem definition

Given an integer array that was sorted in ascending order and then rotated at an unknown pivot, return the index of target, or the language’s conventional absence result.

13.2 Clarifying questions

  1. Are all array values distinct?
  2. Can the array be unrotated or empty?
  3. Is the original ordering strictly ascending?
  4. Can the input array be null?

13.3 Sample answers

  1. Yes. Every value is distinct.
  2. Yes. Zero rotation is valid, and an empty array produces -1 in Java/Python or None in Rust.
  3. Yes. Before rotation, the values were in strictly ascending order.
  4. No. The array is non-null.

13.4 Approach and invariant

The array is not globally sorted, but with distinct values at least one half around any midpoint is sorted. Duplicates would make the sorted-half test ambiguous and can degrade the worst case to linear time.

Use the same boundary convention as the corresponding ordinary binary search:

Java uses the inclusive interval [low,high] and updates high = mid - 1.

Python also uses the inclusive interval [low,high].

Rust uses the half-open interval [low,high), beginning with high = nums.len(). Its last candidate is nums[high - 1], and retaining the left half uses high = middle.

  1. If the midpoint is the target, return it.
  2. If nums[low] <= nums[mid], the left half is sorted. Test whether target lies within its boundaries.
  3. Otherwise the right half is sorted. Test its boundaries.
  4. Keep the half that can contain target and discard the other.
indices:  0  1  2  3  4  5  6
values:  [4, 5, 6, 7, 0, 1, 2]
          L        M        H

left [4..7] is sorted; target 0 is not inside -> keep [4..6]
                      L  M  H
right/remaining search finds 0 at index 4

Invariant: if the target exists and has not been returned, it lies inside the current candidate interval.

The boundary comparisons are asymmetric by design: a target equal to nums[low] belongs left, while nums[mid] was already checked; hence nums[low] <= target && target < nums[mid].

13.5 Minimal solution

import java.util.*;
import org.junit.*;
import org.junit.runner.*;
import static org.junit.Assert.*;

public class RotatedArraySearchSolution {
    static int search(int[] nums, int target) {
        int low = 0;
        int high = nums.length - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] == target) {
                return mid;
            }

            if (nums[low] <= nums[mid]) {
                if (nums[low] <= target && target < nums[mid]) {
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            } else {
                if (nums[mid] < target && target <= nums[high]) {
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            }
        }
        return -1;
    }

    @Test public void emptyArrayHasNoMatch() {
        assertEquals(-1, search(new int[0], 2));
    }

    @Test public void findsOnlyValue() {
        assertEquals(0, search(new int[] {1}, 1));
    }

    @Test public void rejectsMissingValueFromSingleton() {
        assertEquals(-1, search(new int[] {1}, 2));
    }

    @Test public void searchesUnrotatedArray() {
        assertEquals(2, search(new int[] {1, 2, 3, 4}, 3));
    }

    @Test public void findsValueAfterPivot() {
        assertEquals(4, search(new int[] {4, 5, 6, 7, 0, 1, 2}, 0));
    }

    @Test public void findsValueBeforePivot() {
        assertEquals(2, search(new int[] {4, 5, 6, 7, 0, 1, 2}, 6));
    }

    @Test public void findsFirstArrayValue() {
        assertEquals(0, search(new int[] {4, 5, 6, 1, 2, 3}, 4));
    }

    @Test public void findsLastArrayValue() {
        assertEquals(5, search(new int[] {4, 5, 6, 1, 2, 3}, 3));
    }

    @Test public void reportsMissingValue() {
        assertEquals(-1, search(new int[] {4, 5, 6, 7, 0, 1, 2}, 3));
    }

    public static void main(String[] args) {
        JUnitCore.main("RotatedArraySearchSolution");
    }
}
import unittest


def search(nums, target):
    low = 0
    high = len(nums) - 1

    while low <= high:
        middle = low + (high - low) // 2
        if nums[middle] == target:
            return middle

        if nums[low] <= nums[middle]:
            if nums[low] <= target < nums[middle]:
                high = middle - 1
            else:
                low = middle + 1
        else:
            if nums[middle] < target <= nums[high]:
                low = middle + 1
            else:
                high = middle - 1

    return -1


class RotatedArraySearchTests(unittest.TestCase):
    def test_empty_array(self):
        self.assertEqual(-1, search([], 2))

    def test_finds_only_value(self):
        self.assertEqual(0, search([1], 1))

    def test_searches_unrotated_array(self):
        self.assertEqual(2, search([1, 2, 3, 4], 3))

    def test_finds_value_after_pivot(self):
        self.assertEqual(4, search([4, 5, 6, 7, 0, 1, 2], 0))

    def test_finds_value_before_pivot(self):
        self.assertEqual(2, search([4, 5, 6, 7, 0, 1, 2], 6))

    def test_finds_array_boundaries(self):
        self.assertEqual(0, search([4, 5, 6, 1, 2, 3], 4))
        self.assertEqual(5, search([4, 5, 6, 1, 2, 3], 3))

    def test_reports_missing_value(self):
        self.assertEqual(-1, search([4, 5, 6, 7, 0, 1, 2], 3))


if __name__ == "__main__":
    unittest.main()
pub fn search(nums: &[i32], target: i32) -> Option<usize> {
    let mut low = 0;
    let mut high = nums.len();

    while low < high {
        let middle = low + (high - low) / 2;
        if nums[middle] == target {
            return Some(middle);
        }

        if nums[low] <= nums[middle] {
            if nums[low] <= target && target < nums[middle] {
                high = middle;
            } else {
                low = middle + 1;
            }
        } else if nums[middle] < target && target <= nums[high - 1] {
            low = middle + 1;
        } else {
            high = middle;
        }
    }

    None
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn empty_array() {
        assert_eq!(None, search(&[], 2));
    }

    #[test]
    fn finds_only_value() {
        assert_eq!(Some(0), search(&[1], 1));
    }

    #[test]
    fn searches_unrotated_array() {
        assert_eq!(Some(2), search(&[1, 2, 3, 4], 3));
    }

    #[test]
    fn finds_value_after_pivot() {
        assert_eq!(Some(4), search(&[4, 5, 6, 7, 0, 1, 2], 0));
    }

    #[test]
    fn finds_value_before_pivot() {
        assert_eq!(Some(2), search(&[4, 5, 6, 7, 0, 1, 2], 6));
    }

    #[test]
    fn finds_array_boundaries() {
        assert_eq!(Some(0), search(&[4, 5, 6, 1, 2, 3], 4));
        assert_eq!(Some(5), search(&[4, 5, 6, 1, 2, 3], 3));
    }

    #[test]
    fn reports_missing_value() {
        assert_eq!(None, search(&[4, 5, 6, 7, 0, 1, 2], 3));
    }
}

13.6 High-value tests

Input / target Expected Purpose
[4,5,6,7,0,1,2] / 0 4 target after pivot
same / 6 2 target before pivot
same / 3 absent absent
[1,2,3,4] / 3 2 no rotation
[1] / 0 absent one element
[] / 2 absent empty

13.7 Complexity and correctness

Each iteration discards roughly half of the candidate interval, so time is \(O(\log n)\) and space is \(O(1)\).

With distinct values, at least one side of the midpoint is normally ordered. Range checks prove whether the target can be in that sorted side. If it cannot, keeping the other side preserves the invariant; if it can, discarding the other side is safe. Interval updates exclude mid, ensuring progress.

13.8 If the interviewer pushes

  • With duplicates, when nums[low] == nums[mid] == nums[high], shrink both ends; worst-case time becomes \(O(n)\).
  • To find the rotation pivot, binary-search the minimum by comparing nums[mid] with nums[high], then binary-search a selected sorted portion.
  • Ordinary binary search is the special case with no rotation.

13.9 TDD interview script

Confirm distinct values, a valid possibly empty array, a strictly ascending pre-rotation order, zero rotation as valid, and the language’s conventional absence result. Then write this test list:

  1. Empty array
  2. Singleton hit
  3. Singleton miss
  4. Unrotated input
  5. Target after the pivot
  6. Target before the pivot
  7. First position
  8. Last position
  9. Absent target

Run a red–green–refactor cycle for each focused behavior. Start from the familiar binary-search template for the selected language, then let rotated examples drive only the half-selection logic. Rerun the complete example after every change; test indices, not internal bounds.

From book/src, run:

./java/run.sh RotatedArraySearchSolution
./python/run.sh rotated_array_search_solution
./rust/run.sh rotated_array_search_solution

Say the core observation aloud: with distinct values, at least one half around the midpoint is normally sorted. Test whether the target lies inside that half’s inclusive/exclusive boundaries, then retain the only half that can still contain it.

13.9.1 Pseudocode

low = 0
high = nums.length - 1

while low <= high:
    mid = low + (high - low) / 2
    if nums[mid] == target:
        return mid

    if left half is sorted:
        if target is within the left half:
            high = mid - 1
        else:
            low = mid + 1
    else:
        if target is within the right half:
            low = mid + 1
        else:
            high = mid - 1

return -1

Python uses the same inclusive-bound pseudocode, with len(nums) in place of nums.length.

low = 0
high = nums.length

while low < high:
    middle = low + (high - low) / 2
    if nums[middle] == target:
        return Some(middle)

    identify the sorted half
    if target belongs in the retained left half:
        high = middle
    else:
        low = middle + 1

return None

The invariant is: if the target exists and has not been returned, its index remains inside the selected candidate interval.

13.9.2 TDD sequence

Step Test code added Production code added or changed
1. Empty candidates emptyArrayHasNoMatch Initialize inclusive bounds and return -1 when low > high.
2. Midpoint hit findsOnlyValue Compute the overflow-safe midpoint and return it on equality.
3. Midpoint miss rejectsMissingValueFromSingleton Exclude mid with + 1 or - 1, ensuring termination.
4. Ordinary baseline searchesUnrotatedArray Establish the standard binary-search behavior before adding rotation logic.
5. Sorted left half findsValueAfterPivot Detect nums[low] <= nums[mid]; when the target is not in that sorted range, retain the right half.
6. Sorted right half findsValueBeforePivot Handle the complementary case and retain the left half when the target is outside the sorted right range.
7. Inclusive low edge findsFirstArrayValue Include nums[low] in the left-range check and keep index zero reachable.
8. Inclusive high edge findsLastArrayValue Include nums[high] in the right-range check and keep the last index reachable.
9. Exhausted search reportsMissingValue Exercise both half classifications until the candidate interval becomes empty.

The build-out deliberately reuses one inclusive binary-search convention. Boundary-focused tests expose the asymmetric comparisons around a midpoint that has already been checked.