Search in Rotated Sorted Array – Python

🔄 Search in Rotated Sorted Array – Python (Binary Search)

Hi All,

Today I solved an important problem: Search in Rotated Sorted Array using Binary Search.

---

📌 Problem Statement

Given a sorted array that is rotated at some pivot, find the index of a target element.

👉 If not found, return -1.

---

🔍 Examples

Example 1:

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

Output:

4

---

Example 2:

nums = [4, 5, 6, 7, 0, 1, 2]
target = 3

Output:

-1

---

Example 3:

nums = [1]
target = 0

Output:

-1

---

💡 Key Insight

👉 Even though the array is rotated:

• One half of the array is always sorted

---

💡 Approach

🔹 Modified Binary Search

1. Find mid
2. Check which half is sorted:
   • Left half sorted → check if target is inside
   • Right half sorted → check if target is inside

---

🧠 Step-by-Step Logic

• If nums[left] <= nums[mid] → Left part is sorted
• Else → Right part is sorted

Then:

• Decide where to search next

---

💻 Python Code

def search(nums, target):
    left = 0
    right = len(nums) - 1

    while left <= right:
        mid = (left + right) // 2

        if nums[mid] == target:
            return mid

        # Left half sorted
        if nums[left] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1

        # Right half sorted
        else:
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1

    return -1

---

🔍 Dry Run

For:

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

Steps:

• mid = 3 → nums[mid] = 7
• Left sorted → target not in left → go right
• mid = 5 → nums[mid] = 1
• Right sorted → target in right → move left
• mid = 4 → nums[mid] = 0 → found

---

🖥️ Sample Output

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

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

---

⚡ Complexity Analysis

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

---

🧠 Why this is important?

• Combines binary search + logic thinking
• Common interview problem
• Tests understanding of rotated arrays

---

✅ Conclusion

This problem helped me understand:

• Modified binary search
• Handling rotated arrays
• Efficient searching techniques

🚀 Must-know problem for coding interviews!

---