How to Solve: Search in Rotated Sorted Array

How to Solve: Search in Rotated Sorted Array

? Introduction

"This problem appears in 1 out of every 3 onsite interviews—master it, and you prove you can handle non-linear search spaces, a skill that separates L4 from L5 engineers at FAANG."

? WHAT YOU NEED TO KNOW FIRST

Before tackling this problem, ensure you understand: 1. Binary Search – Must know how to implement it from scratch (recursive/iterative). 2. Sorted Arrays & Rotations – Understand how a sorted array behaves when rotated (e.g., [4,5,6,1,2,3]). 3. Edge Cases in Arrays – Empty arrays, single-element arrays, duplicates.

? KEY TECHNIQUES & PATTERNS

? STEP-BY-STEP FRAMEWORK

(Repeatable mental checklist for every "Rotated Sorted Array" problem.)

1. Check for Edge Cases
2. If the array is empty → return -1.

3. If the array has 1 element → check if it matches the target.

4. Initialize Binary Search Pointers

5. left = 0, right = len(nums) - 1.

6. Binary Search Loop (while left <= right)

7. Compute mid = left + (right - left) // 2.

8. If nums[mid] == target → return mid.

9. Determine Which Half is Sorted

10. If nums[left] <= nums[mid] → left half is sorted.
    • If nums[left] <= target < nums[mid] → search left (right = mid - 1).
    • Else → search right (left = mid + 1).

11. Else → right half is sorted.

    • If nums[mid] < target <= nums[right] → search right (left = mid + 1).
    • Else → search left (right = mid - 1).

12. Handle Duplicates (if applicable)

13. If nums[left] == nums[mid] == nums[right] → increment left and decrement right to skip duplicates.

14. Return -1 if Not Found

15. If the loop exits without finding the target → return -1.

✅ WORKED EXAMPLES

Example 1 – Basic (No Duplicates)

Problem: Search for target = 6 in [4,5,6,1,2,3].

Step-by-Step: 1. Edge Case: Array is not empty → proceed. 2. Initialize: left = 0, right = 5. 3. First Iteration (mid = 2):
- nums[2] = 6 == target → return 2.

Code (Python):

def search(nums, target):

    left, right = 0, len(nums) - 1

    while left <= right:

        mid = left + (right - left) // 2

        if nums[mid] == target:

            return mid

        # Left half is sorted

        if nums[left] <= nums[mid]:

            if nums[left] <= target < nums[mid]:

                right = mid - 1

            else:

                left = mid + 1

        # Right half is sorted

        else:

            if nums[mid] < target <= nums[right]:

                left = mid + 1

            else:

                right = mid - 1

    return -1

Time Complexity: O(log n) (standard binary search). Space Complexity: O(1) (iterative approach).

Why This Works: - The array is partially sorted, so we can still apply binary search by checking which half is sorted and whether the target lies in that range.

Example 2 – Medium (With Duplicates)

Problem: Search for target = 2 in [1,1,1,2,1,1].

Step-by-Step: 1. Edge Case: Array is not empty → proceed. 2. Initialize: left = 0, right = 5. 3. First Iteration (mid = 2):
- nums[2] = 1 != target.
- nums[left] == nums[mid] == nums[right] == 1 → skip duplicates (left++, right--). 4. Second Iteration (left = 1, right = 4, mid = 2):
- nums[2] = 1 != target.
- nums[left] = 1 <= nums[mid] = 1 → left half is sorted.
- 1 <= 2 < 1 → False → search right (left = mid + 1). 5. Third Iteration (left = 3, right = 4, mid = 3):
- nums[3] = 2 == target → return 3.

Code (Python):

def search(nums, target):

    left, right = 0, len(nums) - 1

    while left <= right:

        mid = left + (right - left) // 2

        if nums[mid] == target:

            return True

        # Skip duplicates

        if nums[left] == nums[mid] == nums[right]:

            left += 1

            right -= 1

        # Left half is sorted

        elif nums[left] <= nums[mid]:

            if nums[left] <= target < nums[mid]:

                right = mid - 1

            else:

                left = mid + 1

        # Right half is sorted

        else:

            if nums[mid] < target <= nums[right]:

                left = mid + 1

            else:

                right = mid - 1

    return False

Time Complexity: O(n) in worst case (all duplicates), O(log n) average case. Space Complexity: O(1).

Why This Works: - Duplicates break binary search’s invariants, so we skip them while maintaining the search space.

Example 3 – Hard (Find Minimum in Rotated Sorted Array)

Problem: Find the smallest element in [4,5,6,1,2,3].

Step-by-Step: 1. Edge Case: If array is not rotated (nums[left] < nums[right]) → return nums[left]. 2. Initialize: left = 0, right = 5. 3. Binary Search:
- mid = 2 → nums[mid] = 6 > nums[right] = 3 → search right (left = mid + 1).
- mid = 4 → nums[mid] = 2 < nums[right] = 3 → search left (right = mid).
- left == right → return nums[left] = 1.

Code (Python):

def findMin(nums):

    left, right = 0, len(nums) - 1

    while left < right:

        mid = left + (right - left) // 2

        if nums[mid] > nums[right]:

            left = mid + 1

        else:

            right = mid

    return nums[left]

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

Why This Works: - The smallest element is the only point where nums[i] > nums[i+1] in a rotated sorted array.

❌ Common Mistakes

? INTERVIEW TrapS

? 1-Minute Recap

"Alright, let’s lock this in. When you see a rotated sorted array, remember:

1. Binary search still works—just check which half is sorted.
2. If duplicates exist, skip them by moving left and right inward.
3. Edge cases matter: empty array, single element, all duplicates.
4. Time complexity: O(log n) for unique elements, O(n) worst case with duplicates.
5. Practice the follow-ups: finding the minimum, handling duplicates, and optimizing space.

You’ve got this. Now go crush that interview!

? Final Notes

• Practice Variations:
• LeetCode 33. Search in Rotated Sorted Array
• LeetCode 81. Search in Rotated Sorted Array II
• LeetCode 153. Find Minimum in Rotated Sorted Array
• Mock Interview Tip: Always verbalize your thought process—interviewers care more about how you think than the final code.

Now go solve it like a FAANG engineer! ?