CA 20 - Search in Rotated Sorted Array

Problem Search in Rotated Sorted Array You are given a sorted array nums[] with distinct elements, but it may be rotated at an unknown index. Your task is to find the index of a given target. If the target is not present, return -1. You must solve this in O(log n) time. 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 This is a modified Binary Search problem. Even though the array is rotated, at least one half of the array is always sorted. Steps: Initialize left and right pointers Find the middle element Check which half is sorted: If left half is sorted: Check if target lies in this range Otherwise, right half must be sorted: Check if target lies there Narrow down the search accordingly Repeat until the target is found or the search space is exhausted. Complexity: Time Complexity: O(log n) Space Complexity: O(1) def search ( nums , target ): left , right = 0 , len ( nums ) - 1 while left <= right : mid = ( left + ri