← all entries
A-032● Day 322026.06.07mediumleetcode #33neetcode150

Search in Rotated Sorted Array

#array#binary-search
↗ leetcode #33 · search-in-rotated-sorted-array
01

Problem

· problem
P.032

Search in Rotated Sorted Array

↗ leetcode #33

There is an integer array nums sorted in ascending order (with distinct values). Prior to being passed to your function, nums is possibly left rotated at an unknown 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 left rotated by 3 indices 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.

constraints
  • · 1 ≤ nums.length ≤ 5000
  • · -10⁴ ≤ nums[i] ≤ 10⁴
  • · All values in nums are unique
  • · nums is an ascending array that is possibly rotated
  • · -10⁴ ≤ target ≤ 10⁴
// paraphrased summary — see source for full text
examples
example 1input → output
[4,5,6,7,0,1,2]
0
4
example 2input → output
[4,5,6,7,0,1,2]
3
-1
example 3input → output
[1]
0
-1
02

Pre-solve

· pre-solve
● 1list shown→● 2select→● 3reveal
  • ☐
    What does it mean that the array is 'possibly rotated'?
  • ☐
    How does binary search work on a rotated array despite the rotation?
  • ☐
    How do we determine which half of the array (left or right of mid) is sorted?
  • ☐
    Once we identify which half is sorted, what should we do next?
  • ☐
    Is the array guaranteed to be rotated?
  • ☐
    Since the array has at most 5000 elements, can we just use linear search?
  • ☐
    Can the array contain duplicate values?
check the items you would ask, then press confirm
// session-only state — refresh resets (repeatable practice)
03

Logic Structure

· logic
● 1slots shown→● 2pick per slot→● 3reveal
// pick one code line per slot to assemble the algorithm flow. no typing — just the logic skeleton.
step 1· Initialize pointers
○
l, r = 0, len(nums) - 1
○
l, r = 0, len(nums)
○
l, r = 1, len(nums) - 1
step 2· Binary search loop
○
while l <= r:
○
while l < r:
○
while l < len(nums) and r >= 0:
step 3· Calculate midpoint│ nested
○
mid = (l + r) // 2
○
mid = (l + r) / 2
○
mid = r - (r - l) // 2
step 4· Check if target found│ nested
○
if target == nums[mid]:
○
if target < nums[mid]:
○
if target >= nums[mid]:
step 5· Determine sorted portion│ nested
○
if nums[l] <= nums[mid]:
○
if nums[mid] <= nums[r]:
○
if nums[l] > nums[mid]:
step 6· Adjust search range│ │ nested
○
if target > nums[mid] or target < nums[l]:
○
if target > nums[mid] or target > nums[l]:
○
if target < nums[mid] or target < nums[l]:
step 7· Return not found
○
return -1
○
return 0
○
return None
pick one option per slot
// format: slot — recursive / DP patterns use ordering / state-first formats. ADR-08 follow-up.
04

Solve · Trace

· solve
solution.py
1
class Solution:
2
    def search(self, nums: List[int], target: int) -> int:
3
        l, r = 0, len(nums) - 1
4
5
        while l <= r:
6
            mid = (l + r) // 2
7
            if target == nums[mid]:
8
                return mid
9
10
            # left sorted portion
11
            if nums[l] <= nums[mid]:
12
                if target > nums[mid] or target < nums[l]:
13
                    l = mid + 1
14
                else:
15
                    r = mid - 1
16
            # right sorted portion
17
            else:
18
                if target < nums[mid] or target > nums[r]:
19
                    r = mid - 1
20
                else:
21
                    l = mid + 1
22
        return -1
mental dry-run cases
// walk each case in your head; expand the worked example below if stuck.
case 1
[4,5,6,7,0,1,2]
0
→
4
case 2
[4,5,6,7,0,1,2]
3
→
-1
case 3
[1]
0
→
-1
// UI does not walk-through — you do the dry-run mentally. Expand the worked example if stuck.