Search in Rotated Sorted Array

Problem Statement

Given a sorted array that has been rotated at some pivot, and a target value, find the index of the target element.

If the target is not present, return -1.

---

Examples

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

Output
4

---

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

Output
-1

---

Approach Using Modified Binary Search

Even though the array is rotated, one half of the array is always sorted. We can use this property to search efficiently.

---

Steps

1 Initialize left and right pointers
2 Find the middle element
3 If middle element is the target return index
4 Check which half is sorted
5 If left half is sorted

• Check if target lies in this range
• If yes move right pointer
• Else move left pointer 6 If right half is sorted
• Check if target lies in this range
• If yes move left pointer
• Else move right pointer 7 Repeat until element is found or search space is empty

---

Code

```python id="rot1"
def search(arr, target):
left = 0
right = len(arr) - 1

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

    if arr[mid] == target:
        return mid

    if arr[left] <= arr[mid]:
        if arr[left] <= target < arr[mid]:
            right = mid - 1
        else:
            left = mid + 1
    else:
        if arr[mid] < target <= arr[right]:
            left = mid + 1
        else:
            right = mid - 1

return -1

---

## Explanation

The algorithm identifies which part of the array is sorted and checks if the target lies in that range. Based on that, it reduces the search space.

---

## Expected Output

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

Output
4

---

## Conclusion

This problem is a variation of binary search and helps in understanding how to handle rotated arrays. It is commonly asked in interviews and improves logical thinking.

Practice this problem with different rotated arrays to master the concept.