Search in Rotated Sorted Array

Introduction

Searching in a rotated sorted array is a common problem in data structures and algorithms. It combines concepts of binary search and array manipulation.

---

Problem Statement

Given a rotated sorted array and a target value, return the index of the target if it exists. Otherwise, return -1.

A rotated array means the sorted array is shifted at some pivot.

Example:
[4, 5, 6, 7, 0, 1, 2]

---

Approach (Binary Search)

We can solve this efficiently using Binary Search:

1. Find the middle element
2. Check which part (left or right) is sorted
3. Decide whether the target lies in the sorted part
4. Adjust search range accordingly
5. Repeat until found or search space is empty

---

Python Code

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

    while left <= right:
        mid = (left + right) // 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


## Example:
   Input
 nums = [4,5,6,7]
target = 0

   output
    4