33. Search in Rotated Sorted Array

Array
Binary Search

TIME

O(log n)

SPACE

O(1)

Intuition

Even after rotation, at least one half of the current search interval is sorted.

At each step, compare nums[left], nums[mid], and nums[right] to determine which half is sorted. If the target falls inside the sorted half, continue searching there. Otherwise, discard that half and search the other side.

Approach

Set left = 0 and right = len(nums) - 1.
While left <= right:
- compute mid
- if nums[mid] == target, return mid
- if the left half is sorted:
  - search left if target is between nums[left] and nums[mid]
  - otherwise search right
- otherwise the right half is sorted:
  - search right if target is between nums[mid] and nums[right]
  - otherwise search left
Return -1 if the target is not found.

Complexity

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

Edge Cases

Single-element array
Array is not rotated
Target is at the pivot
Target is absent
Target is at either boundary

Code

from typing import List


class Solution:
    def search(self, nums: List[int], target: int) -> int:
        """
        33. Search in Rotated Sorted Array
        Time: O(log n)
        Space: O(1)
        """
        left = 0
        right = len(nums) - 1

        while left <= right:
            mid = (left + right) // 2

            if nums[mid] == target:
                return mid

            if nums[left] <= nums[mid]:
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            else:
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1

        return -1

/**
 * 33. Search in Rotated Sorted Array
 * Time: O(log n)
 * Space: O(1)
 */
class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] == target) {
                return mid;
            }

            if (nums[left] <= nums[mid]) {
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }

        return -1;
    }
}