Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns in Python

Solution: Search in Rotated Sorted Array

Understand how to apply a modified binary search to locate a target value in a rotated sorted array. Explore step-by-step solutions that utilize the property of sorted halves and efficient pointer adjustments to achieve efficient O(log n) time complexity and minimal space usage. This lesson guides you through naive and optimized approaches, explaining tradeoffs and final implementation.

We'll cover the following...

Statement

You are given a sorted integer array, nums, and an integer, target. The array may have been rotated by an arbitrary number. Your task is to find and return the index of target in this array. If target does not exist, return -1.

An original sorted array before rotation is given below:

g array 1 10 20 47 59 63 75 88 99 107 120 133 155 162 176 188 199 200 210 222

After rotating this array 6 times, it changes to:

g array 176 188 199 200 210 222 1 10 20 47 59 63 75 88 99 107 120 133 155 162

Constraints:

  • All values in nums are unique.
  • The values in nums are sorted in ascending order.
  • The array may have been rotated by some arbitrary number.
  • 1≤1 \leq nums.length ≤1000\leq 1000
  • −104≤-10^4 \leq nums[i] ≤104\leq 10^4
  • −104≤-10^4 \leq target ≤104\leq 10^4
...