Free AI LeetCode Communication Coach — Search in Rotated Sorted Array

The problem

nums is sorted then rotated. Search for target in O(log n). Return index or -1.

Example: nums = [4,5,6,7,0,1,2], target = 0 → 4

Sorted-half decision is the key sentence.

left, right = 0, 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

How to explain it

1. 1. Restate

   Say the problem in your own words.

   One or two sentences. Show you understood the input, the output, and the goal — not that you memorised the prompt.

2. 2. Approach

   Name the method before you code.

   Brute force first if you need it, then the structure you will use: hash map, two pointers, stack, binary search.

3. 3. Example

   Walk one concrete input.

   Pick small numbers. Say what you store, what you compare, and what you return. Interviewers follow an example more easily than abstract talk.

4. 4. Time and space

   One sentence each.

   After the example, before you claim you are done. “Time is O(n) because we scan once. Space is O(n) for the map.”

5. 5. Edge cases

   Name at least one unusual input.

   Empty input, duplicates, already sorted, overflow. Invite a follow-up: “I would also check …”

• “I check which half is sorted.”
• “Then I ask if the target is inside that range.”

Practise out loud

1. 1. Restate

   The sorted array was rotated. I still need the index of target in logarithmic time.

2. 2. Approach

   I binary search, but at mid I check which half is sorted. Then I see if the target lies in that sorted half; otherwise I search the other half.

3. 3. Example

   On 4,5,6,7,0,1,2 target 0 — mid might be 7; the right half is not fully sorted, the left is. Target is not in 4..7, so I search right and find 0.

4. 4. Time and space

   Time is O(log n). Space is O(1).

5. 5. Edge cases

   I would check a non-rotated array and a single-element array.

Common mistakes when explaining Search in Rotated Sorted Array

• Not saying which half is sorted.
• Treating it as plain binary search without the rotation case.