Search in Rotated Sorted Array

Mediumbinary-searcharray
Category: Binary Search
Companies that ask this question:
AmazonMicrosoftFacebookLinkedInBloomberg
LeetCode →NeetCode →

Approach

Search in Rotated Sorted Array

Problem Statement

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). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

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.

Examples

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

Intuition

In a rotated sorted array, one half is always sorted. The key is to:

  1. Identify which half is sorted
  2. Check if target is in the sorted half
  3. Search the appropriate half

This maintains O(log n) time by eliminating half the array each iteration.

Pattern Recognition

This is Modified Binary Search on Rotated Array with:

  • Partially sorted input
  • Need to find specific target
  • Identify sorted portion
  • Make decision based on target's potential location

Approach

  1. Initialize: left = 0, right = n - 1

  2. Binary Search Loop: While left <= right:

    • Calculate mid = left + (right - left) / 2
    • If nums[mid] == target: Return mid

  3. Identify Sorted Half:

    • If nums[left] <= nums[mid]: Left half is sorted
      • If nums[left] <= target < nums[mid]: Search left
      • Else: Search right
    • Else: Right half is sorted
      • If nums[mid] < target <= nums[right]: Search right
      • Else: Search left

  4. Not Found: Return -1

Edge Cases

  • Array not rotated
  • Single element
  • Target at rotation point
  • Target not in array

Complexity Analysis

  • Time Complexity: O(log n)
    • Binary search with modified logic
  • Space Complexity: O(1)
    • Only using pointers

Solution

java
1class Solution {
2    public int search(int[] nums, int target) {
3        int left = 0;
4        int right = nums.length - 1;
5
6        while (left <= right) {
7            int mid = left + (right - left) / 2;
8
9            if (nums[mid] == target) {
10                return mid;
11            }
12
13            // Determine which half is sorted
14            if (nums[left] <= nums[mid]) {
15                // Left half is sorted
16                if (nums[left] <= target && target < nums[mid]) {
17                    // Target is in sorted left half
18                    right = mid - 1;
19                } else {
20                    // Target is in right half
21                    left = mid + 1;
22                }
23            } else {
24                // Right half is sorted
25                if (nums[mid] < target && target <= nums[right]) {
26                    // Target is in sorted right half
27                    left = mid + 1;
28                } else {
29                    // Target is in left half
30                    right = mid - 1;
31                }
32            }
33        }
34
35        return -1;
36    }
37}
38
Loading visualizer...