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: Find the middle element Check which part (left or right) is sorted Decide whether the target lies in the sorted part Adjust search range accordingly 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 <=