🔍 Search in Rotated Sorted Array (Binary Search Variation)

This problem is a classic variation of Binary Search, where the array is sorted but rotated at some unknown pivot.

---

📌 Problem Statement

You are given a sorted array that has been rotated at an unknown index.

Given a target value, return its index if found, otherwise return -1.

The solution must run in O(log n) time.

---

🔍 Examples

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

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

Example 3:
Input: nums = [1], target = 0
Output: -1

---

🧠 Intuition

Even though the array is rotated, one key property still holds:

👉 At least one half of the array is always sorted.

We can use this property to decide where to search.

---

🔄 Approach (Modified Binary Search)

Step-by-Step:

1. Initialize:

• low = 0
• high = n - 1

1. While low <= high:

• Find mid

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

2. Check which half is sorted:

• If left half is sorted (nums[low] <= nums[mid]):

  • If target lies in this range → search left
  • Else → search right

• Else (right half is sorted):

  • If target lies in this range → search right
  • Else → search left

---

💻 Python Code

```python id="rs1"
def search(nums, target):
low, high = 0, len(nums) - 1

while low <= high:
    mid = (low + high) // 2

    if nums[mid] == target:
        return mid

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

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

return -1

print(search([4, 5, 6, 7, 0, 1, 2], 0))

---

🧾 Dry Run

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

* low = 0, high = 6 → mid = 3 (7)

* Left half sorted → target not in range → go right

* low = 4, high = 6 → mid = 5 (1)

* Right half sorted → target in range → go left

* low = 4, high = 4 → mid = 4 (0)

👉 Found at index 4

---

⚡ Complexity

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

---

🔥 Why This Works

* Uses binary search efficiently
* Leverages sorted half property
* Avoids full traversal

---

⚠️ Edge Cases

* Single element array
* Target not present
* Pivot at start or end

---

🏁 Conclusion

This problem teaches:

* Advanced binary search logic
* Handling rotated arrays
* Efficient searching in modified structures