Search in rotated sorted array

Problem Link

search-in-rotated-sorted-array

Problem Statement

You are given a sorted array of distinct integers which is possibly rotated at an unknown pivot index k (where 1 <= k < nums.length).

The array nums was originally sorted in ascending order, but after rotation, it becomes:

[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]

Given such an array and a target value, return the index of the target if it exists. Otherwise, return -1.

The algorithm must run in O(log n) time.

Examples

• Input: nums = [4,5,6,7,0,1,2], target = 0
  Output: 4

• Input: nums = [4,5,6,7,0,1,2], target = 3
  Output: -1

• Input: nums = [1], target = 0
  Output: -1

Constraints

• 1 <= nums.length <= 5000

• -10^4 <= nums[i] <= 10^4

• All elements in nums are unique

• nums is a sorted array that is possibly rotated

• -10^4 <= target <= 10^4

Intuition

When a sorted array is rotated at some pivot, it still contains two sorted subarrays. The key idea is:

1. Find the pivot point (index of maximum element). This splits the array into two sorted halves.

2. Then, apply binary search on the appropriate half based on the target's value.

This approach ensures that the overall time complexity remains O(log n).

Approach

1. Find the Pivot:

   • The pivot is the index of the largest element.

   • It satisfies:

     • arr[mid] > arr[mid + 1] → mid is the pivot

     • arr[mid] < arr[mid - 1] → mid - 1 is the pivot

   • Use binary search logic to find such an index.

2. Search Using Binary Search:

   • If pivot is -1, the array is not rotated, perform normal binary search.

   • If arr[pivot] == target, return pivot.

   • If target lies in the left half (arr[0] to arr[pivot]), search there.

   • Otherwise, search in the right half (arr[pivot + 1] to end).

Code in Java

class Solution {
    public int search(int[] arr, int target) {
        int pivot = findPeak(arr);
        
        if (pivot == -1) {
            // Not rotated
            return binarySearch(arr, target, 0, arr.length - 1);
        }

        if (arr[pivot] == target) return pivot;

        int ans = binarySearch(arr, target, 0, pivot);
        if (ans == -1) {
            ans = binarySearch(arr, target, pivot + 1, arr.length - 1);
        }

        return ans;
    }

    public int binarySearch(int[] nums, int target, int s, int e) {
        while (s <= e) {
            int m = s + (e - s) / 2;

            if (nums[m] == target) {
                return m;
            } else if (nums[m] > target) {
                e = m - 1;
            } else {
                s = m + 1;
            }
        }

        return -1;
    }

    public int findPeak(int[] arr) {
        int low = 0;
        int high = arr.length - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2;

            if (mid < high && arr[mid] > arr[mid + 1]) {
                return mid;
            }

            if (mid > low && arr[mid] < arr[mid - 1]) {
                return mid - 1;
            }

            if (arr[low] >= arr[mid]) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        return -1;
    }
}

Time and Space Complexity

• Time Complexity:

  • Pivot search: O(log n)

  • Binary search: O(log n)

  • Total: O(log n)

• Space Complexity:
  O(1) — constant space usage

Dry Run

Input:

arr = [4, 5, 6, 7, 0, 1, 2], target = 0

Step 1: Find Pivot

• mid = 3 → arr[3] = 7, arr[4] = 0 → 7 > 0 → pivot = 3

Step 2: Search

• arr[pivot] = 7 ≠ target

• Check right half: binarySearch(arr, 4, 6, 0)

• mid = 5 → arr[5] = 1 > target → move left

• mid = 4 → arr[4] = 0 == target → return 4

Output: 4

Conclusion

This problem demonstrates how classic binary search can be adapted for rotated arrays. By locating the pivot point and narrowing down the target range, we maintain the desired logarithmic complexity. This pattern is commonly used in variations of rotated sorted array problems.