Binary Search in Rotated Sorted Array Explained (LeetCode 33) | Python O(log n) Solution

Binary Search in Rotated Sorted Array (LeetCode 33)

Binary Search in a Rotated Sorted Array is a classic interview problem that tests your understanding of binary search beyond the basics. In this article, we’ll break down the logic, intuition, and implementation of an efficient O(log n) solution using Python.

---

🔍 Problem Overview

You are given a rotated sorted array of distinct integers and a target value. Your task is to return the index of the target if it exists, otherwise return -1.

Example:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

The challenge arises because the array is sorted but rotated at an unknown pivot, which means traditional binary search cannot be applied directly.

---

🧠 Key Insight

At any point in a rotated sorted array, at least one half is always sorted. We use this fact to decide which side of the array to discard during binary search.

• Identify whether the left or right half is sorted
• Check if the target lies within the sorted half
• Discard the unnecessary half

---

⚙️ Python Implementation

Below is an optimized and clean Python solution using binary search:

class Solution:
    def search(self, nums, target):
        s, e = 0, len(nums) - 1

        while s <= e:
            mid = (s + e) // 2

            if nums[mid] == target:
                return mid

            # Left half is sorted
            if nums[s] <= nums[mid]:
                if nums[s] <= target < nums[mid]:
                    e = mid - 1
                else:
                    s = mid + 1

            # Right half is sorted
            else:
                if nums[mid] < target <= nums[e]:
                    s = mid + 1
                else:
                    e = mid - 1

        return -1

---

🧪 Example Walkthrough

For the array [4,5,6,7,0,1,2]:

• Mid = 7 → left half is sorted
• Target (0) not in left range → move right
• Repeat until target is found

This approach ensures we always reduce the search space by half.

---

⏱️ Time & Space Complexity

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

---

📌 Common Mistakes to Avoid

• Forgetting that only one half is guaranteed to be sorted
• Incorrect boundary checks with target
• Using linear search instead of binary search

---

🔗 Complete Source Code

You can find the full and tested solution on GitHub:

👉 Binary Search in Rotated Sorted Array – Python Solution

---

✅ Final Thoughts

This problem is a great example of how understanding array properties can turn a seemingly complex problem into a clean and efficient solution. Mastering this pattern will help you solve many advanced binary search problems.

Happy Coding 🚀