Command Palette

Search for a command to run...

Hectal
Problem 11.4 · Binary SearchMedium

Search in Rotated Sorted Array

PatternBinary Search on an Index

What it teaches: Binary search when sortedness is broken at one point: one half is always sorted, so decide using that half.

Practise it on judges as “Search in Rotated Sorted Array”.

The problem

A sorted array of distinct values was rotated at an unknown pivot (e.g. [0,1,2,4,5,6,7] → [4,5,6,7,0,1,2]). Return the index of target 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

  • 1 ≤ n ≤ 5000
  • Distinct values

Pattern clues in the wording

  • → Sorted then rotated
  • → O(log n) required

These clues point to Binary Search on an Index: In sorted data, check the middle and throw away the half that can't contain the answer.

Stuck? Take one hint at a time

Solution.java · starter
class Solution {
    public int search(int[] nums, int target) {
        return -1;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
nums = [4,5,6,7,0,1,2]
target = 0
4
2
nums = [4,5,6,7,0,1,2]
target = 3
-1
3
nums = [1]
target = 0
-1

+ 2 hidden tests the code runner will check

From slow to fast

Approaches

1. Optimal: pick the sorted half · O(log n)
1

Optimal: pick the sorted half

Time O(log n) Space O(1)

If nums[lo] <= nums[mid], the left half is sorted: go left when nums[lo] <= target < nums[mid], else right. Otherwise the right half is sorted: go right when nums[mid] < target <= nums[hi], else left.

▶ Dry run: Finding 0nums = [4, 5, 6, 7, 0, 1, 2], target = 0
4
0
↑lo
5
1
6
2
7
3
↑mid
0
4
1
5
2
6
↑hi

Step 1/3mid = 3 (7). Left half 4..7 is sorted, and 0 isn't in [4, 7): go right. lo = 4.

Approach 1
class Solution {
    public int search(int[] nums, int target) {
        int lo = 0, hi = nums.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 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;
    }
}

Verdict: One pass of binary search.

Before you submit

Edge cases and common mistakes

Test these inputs

  • Not rotated at all
  • Rotated by one
  • Two elements
  • Target at the pivot

Mistakes people make

  • nums[lo] < nums[mid] instead of <= (fails when lo == mid).
  • Off-by-one in the inclusive/exclusive range checks.

Interview

Follow-up questions

What if duplicates are allowed?