How do you approach Search in Rotated Sorted Array?

Use binary search, but determine which half is sorted.

What is the time complexity of Search in Rotated Sorted Array?

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

What are common mistakes on Search in Rotated Sorted Array?

Computing the midpoint as (low + high) / 2. In a fixed-width integer language that overflows on large ranges; low + (high - low) / 2 does not. An update that fails to shrink the range, which spins forever on a two-element window. Answering "does it exist" when the question asked for the first or last occurrence - the boundary variants need a different post-loop return.

gitGood.dev

← Back to problems

Search in Rotated Sorted Array

MediumAlgorithms

Description

There is an integer array `nums` sorted in ascending order (with **distinct** values). Prior to being passed to your function, `nums` is **possibly rotated** at an unknown pivot index `k` (`1 <= k < nums.length`) such that the resulting array is `[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]` (**0-indexed**). 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 in `nums`. You must write an algorithm with O(log n) runtime complexity.

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

Example 3

Input: nums = [1], target = 0

Output: -1

Constraints

- 1 <= nums.length <= 5000 - -10^4 <= nums[i] <= 10^4 - All values of nums are unique. - nums is an ascending array that is possibly rotated. - -10^4 <= target <= 10^4

Search in Rotated Sorted Array: approach, complexity and pitfalls

A medium binary search problem, graded against 6 test cases (3 of them hidden).

The pattern: Binary Search

Halving a search space each step - on sorted arrays, and on answers themselves.

Reach for it when you see: A sorted input, or a monotonic "is this value feasible?" predicate you can binary search over.

More Binary Searchproblems →

If you are stuck

Show the 3-step hint ladder

Use binary search, but determine which half is sorted.
If the left half is sorted and target is in that range, search left; otherwise, search right.
Apply the same logic for the right half.

The optimal approach

Show the approach: Modified Binary Search

At each step, determine which half is sorted. Then check if the target lies in the sorted half and narrow the search accordingly.

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

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Binary Search mistakes

These apply to the pattern as a whole, not just this problem.

Computing the midpoint as `(low + high) / 2`. In a fixed-width integer language that overflows on large ranges; `low + (high - low) / 2` does not.
An update that fails to shrink the range, which spins forever on a two-element window.
Answering "does it exist" when the question asked for the first or last occurrence - the boundary variants need a different post-loop return.

← Back to problems

Search in Rotated Sorted Array

MediumAlgorithms

Description

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

Example 3

Input: nums = [1], target = 0

Output: -1

Constraints

- 1 <= nums.length <= 5000 - -10^4 <= nums[i] <= 10^4 - All values of nums are unique. - nums is an ascending array that is possibly rotated. - -10^4 <= target <= 10^4

Search in Rotated Sorted Array: approach, complexity and pitfalls

A medium binary search problem, graded against 6 test cases (3 of them hidden).

The pattern: Binary Search

Halving a search space each step - on sorted arrays, and on answers themselves.

Reach for it when you see: A sorted input, or a monotonic "is this value feasible?" predicate you can binary search over.

More Binary Searchproblems →

If you are stuck

Show the 3-step hint ladder

Use binary search, but determine which half is sorted.
If the left half is sorted and target is in that range, search left; otherwise, search right.
Apply the same logic for the right half.

The optimal approach

Show the approach: Modified Binary Search

At each step, determine which half is sorted. Then check if the target lies in the sorted half and narrow the search accordingly.

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

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Binary Search mistakes

These apply to the pattern as a whole, not just this problem.

Computing the midpoint as `(low + high) / 2`. In a fixed-width integer language that overflows on large ranges; `low + (high - low) / 2` does not.
An update that fails to shrink the range, which spins forever on a two-element window.
Answering "does it exist" when the question asked for the first or last occurrence - the boundary variants need a different post-loop return.