💬 Discord
Sign In
NeetCode #285LC-33MediumBinary SearchBlind 75NC 150NC 250
← Back to All Problems

#285 · #33 · Search in Rotated Sorted Array(搜索旋转排序数组)

📌 Problem Statement & Constraints

Given a rotated sorted array of distinct integers nums and a target, return the index of target or -1. Constraints: 1 <= nums.length <= 5000, -10^4 <= nums[i] <= 10^4, all values distinct. The algorithm must run in O(log n).

💡 Core Algorithmic Approaches

  1. At any midpoint, one of the two halves is properly sorted. Determine which by comparing nums[lo] with nums[mid].
  2. If the left half is sorted, check whether the target lies within it; if so, search there, otherwise search the right half.
  3. Symmetrically for the right half. This gives a single binary search.
  4. The key insight is that the rotation point can be located implicitly through the sorted-half test.

💻 Benchmark Python3 Implementation

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        lo, hi = 0, len(nums) - 1
        while lo <= hi:
            mid = (lo + hi) // 2
            if nums[mid] == target:
                return mid
            if nums[lo] <= nums[mid]:          # left half is sorted
                if nums[lo] <= target < nums[mid]:
                    hi = mid - 1
                else:
                    lo = mid + 1
            else:                              # right half is sorted
                if nums[mid] < target <= nums[hi]:
                    lo = mid + 1
                else:
                    hi = mid - 1
        return -1

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(log n): one binary search with O(1) work per step.
💾 Space Complexity
O(1): three indices.

⚠️ Interview Pitfalls & Follow-ups

  • Using nums[lo] < nums[mid] instead of <=: with nums[lo] == nums[mid] (possible when the subarray has one element) the strict version misclassifies the half.
  • Forgetting that only one half is sorted: assuming both halves are sorted leads to an incorrect comparison.
  • Using inclusive comparisons on both ends of the target range: the range test is nums[lo] <= target < nums[mid], half-open, which correctly excludes mid (already checked).
  • Falling back to a linear scan: correct but O(n), defeating the O(log n) requirement.