Search in Rotated Sorted Array Using Binary Search

Problem Statement: Given a sorted array that has been rotated at an unknown index, find the index of a target element. If the target is not present, return -1. Example: Input: nums = [4,5,6,7,0,1,2], target = 0 Output: 4 Input: nums = [4,5,6,7,0,1,2], target = 3 Output: -1 Approach: We use a modified Binary Search. In a rotated sorted array, at least one half is always sorted. By checking which half is sorted, we can decide where the target might lie and reduce the search space. Code: def search(nums, target): low = 0 high = len(nums) - 1 while low <= high: mid = (low + high) // 2 if nums[mid] == target: return mid if nums[low] <= nums[mid]: if nums[low] <= target < nums[mid]: high = mid - 1 else: low = mid + 1 else: if nums[mid] < target <= nums[high]: low = mid + 1 else: high = mid - 1 return -1 Explanation: The algorithm first checks the middle element. Then it determines whether the left half or right half is sorted. Based on where the target lies, it continues th