{"id":515,"date":"2025-07-03T12:22:02","date_gmt":"2025-07-03T06:52:02","guid":{"rendered":"https:\/\/codeanddebug.in\/blog\/?p=515"},"modified":"2025-07-03T12:22:04","modified_gmt":"2025-07-03T06:52:04","slug":"search-in-rotated-sorted-array","status":"publish","type":"post","link":"https:\/\/codeanddebug.in\/blog\/search-in-rotated-sorted-array\/","title":{"rendered":"Search in Rotated Sorted Array | Leetcode 33 | Optimal Binary Search"},"content":{"rendered":"\n

There is an integer array nums<\/code> sorted in ascending order (with distinct<\/strong> values).<\/p>\n\n\n\n

Prior to being passed to your function, nums<\/code> is possibly rotated<\/strong> at an unknown pivot index k<\/code> (1 <= k < nums.length<\/code>) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]<\/code> (0-indexed<\/strong>). For example, [0,1,2,4,5,6,7]<\/code> might be rotated at pivot index 3<\/code> and become [4,5,6,7,0,1,2]<\/code>.<\/p>\n\n\n\n

Given the array nums<\/code> after<\/strong> the possible rotation and an integer target<\/code>, return the index of <\/em>target<\/code> if it is in <\/em>nums<\/code>, or <\/em>-1<\/code> if it is not in <\/em>nums<\/code>.<\/p>\n\n\n\n

You must write an algorithm with O(log n)<\/code> runtime complexity.<\/p>\n\n\n\n

Here’s the [Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

Input:<\/strong> nums = [4,5,6,7,0,1,2], target = 0
Output:<\/strong> 4<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> nums = [4,5,6,7,0,1,2], target = 3
Output:<\/strong> -1<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
Input:<\/strong> nums = [1], target = 0
Output:<\/strong> -1<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n