## Problem Statement There is an integer array nums sorted in ascending order (with distinct values). Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2]. Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums. You must write an algorithm with O(log n) runtime complexity. - Constraints: - `1 <= nums.length <= 5000` - `-104 <= nums[i] <= 104` - `All values of nums are unique.` - `nums is an ascending array that is possibly rotated.` - `-104 <= target <= 104` - `pivot index k - (1 <= k < nums.length)` - Examples: - Example 1: ```python Input: nums = [4,5,6,7,0,1,2], target = 0 Output: 4 ``` - Example 2: ```python Input: nums = [4,5,6,7,0,1,2], target = 3 Output: -1 ``` ## Solutions ### Approach 1 The "Search in Rotated Sorted Array" problem on LeetCode is a `classic binary search problem with a twist`. It involves finding a target value in a sorted array that has been rotated at an unknown pivot point. ```python class Solution(object): def binary_search(self, nums, target): left, right = 0, len(nums) - 1 while left <= right: mid = left + (right - left) // 2 if nums[mid] == target: return mid elif nums[mid] < target: left = mid + 1 else: right = mid - 1 return -1 def search(self, nums, target): # search_rotated_array if not nums: return -1 left, right = 0, len(nums) - 1 # Use a while loop to perform binary search within the rotated sorted array. while left <= right: mid = (left + right) // 2 if nums[mid] == target: return mid # Check if the left side is sorted if nums[left] <= nums[mid]: # Check if the target is in the left side if nums[left] <= target <= nums[mid]: right = mid - 1 else: left = mid + 1 # Check if the right side is sorted else: # Check if the target is in the right side if nums[mid] <= target <= nums[right]: left = mid + 1 else: right = mid - 1 return -1 ``` Here's a tabular comparison of the differences between binary search in a regular sorted array and binary search in a rotated sorted array: | Aspect | Binary Search in Regular Sorted Array | Binary Search in Rotated Sorted Array | |--------------------------------------|--------------------------------------|---------------------------------------| | Input Array | Assumes the input array is sorted in ascending order. | Handles arrays that are sorted but have been rotated at an unknown pivot point. | | Additional Checks for Rotation | Does not have additional checks for rotation because it assumes a normal sorted array. | Includes checks to determine whether the left or right half is sorted due to rotation. | | Typical Example | `[1, 2, 3, 4, 5, 6, 7, 8, 9]` | `[6, 7, 8, 9, 1, 2, 3, 4, 5]` | | Example Usage | `binary_search(regular_sorted_array, target)` | `search_rotated_array(rotated_sorted_array, target)` | This table summarizes the key differences between the two binary search functions and how they are used in different contexts. ## References 1. [LeetCode - Search in a rotated sorted array](https://leetcode.com/problems/search-in-rotated-sorted-array/)