33. Search in Rotated Sorted Array

How to solve Search in Rotated Sorted Array (LeetCode 33): the approach in brief

The problem

There is an integer array nums sorted in ascending order (with distinct values).

Pattern

Search in Rotated Sorted Array is a Binary Search Patterns problem, in the Find Min/Max in Rotated Sorted Array subpattern. The pattern covers standard binary search, rotated arrays, first/last occurrence, and search on answer space

Master binary search in rotated sorted arrays. Find minimum, search elements, and handle duplicates.

Approach outline

1. Consider how binary search can be adapted to work efficiently on arrays that are not fully sorted in the traditional sense.
2. Observe that even though the array is rotated, one half of the array (left or right) remains sorted at any point during your search.
3. Use the fact that the sorted half can help determine whether the target lies within that half or the other half, guiding your search boundaries.

Complexity

The reference solution runs in O(logn) time and O(1) space.

Asked at

Search in Rotated Sorted Array has been reported in interviews at Amazon, Facebook, Microsoft, LinkedIn, Oracle, Apple, Bloomberg, Nvidia.