Binary Search
Search in Rotated Sorted Array
medium
Count: 10
DESCRIPTION (inspired by Leetcode.com)
You are given a sorted array that has been rotated at an unknown pivot point, along with a target value. Develop an algorithm to locate the index of the target value in the array. If the target is not present, return -1. The algorithm should have a time complexity of O(log n).
Note:
- The array was originally sorted in ascending order before being rotated.
- The rotation could be at any index, including 0 (no rotation).
- You may assume there are no duplicate elements in the array.
Example 1:
Input:
nums = [4,5,6,7,0,1,2], target = 0
Output: 4 (The index of 0 in the array)
Example 2:
Input:
nums = [4,5,6,7,0,1,2], target = 3
Output: -1 (3 is not in the array)
Explanation
The fact that this question is asking for a O(log n) solution is a hint that we should be using binary search to solve it. If we can iteratively search for our target value in the array while reducing the relevant search space by half in each iteration, then we can achieve the desired time complexity.
So let's first look at an example of a rotated sorted array and see if we can notice anything that will help us do so.
Reducing the Search Space
The visual below shows the same sorted array rotated at different points, including no rotation at all.
If we draw a line down the middle element of each array, this splits the array into two halves. Notice how at least one of the halves is always sorted in ascending order, shown in dark green in the visual.
We'll learn which half to choose when both halves are sorted (like in the first and fourth arrays) in the next step, when we learn how to determine the sorted half.
We'll also mention why the middle element itself is greyed out a little later.
The fact that one half of the array is always sorted is great for our goal, because we can quickly tell if our target falls within the range of that half by comparing the target with its endpoints.
If our target 3 falls within the range of the sorted half, we can confidently discard the other half of the array:
Otherwise, we can discard the sorted half and continue our search in the other half.
So we've accomplished our goal - we used the fact the one half of the array is always sorted to reduce our search space by half.
We can now apply the same logic as above to the half of the array we didn't discard. But first, let's see how to determine which half of the array is sorted.
Determining the Sorted Half
In a regular, unrotated, sorted array, the first element will always be less (or equal to) the middle element. However, this isn't always true for a rotated sorted array.
In a rotated search array, the middle element mid will sometimes be less than the first element left. This happens when the rotation occurs somewhere between left and mid, meaning the right half of the array is sorted.
Notice how in the first array, both halves of the array are actually sorted, as the rotation occurs right at mid. However, we still choose the right half as the sorted half because mid < left.
However, if the middle element mid is greater than the first element left, we know that the left half of the array is sorted, like shown in the 3 examples below.
Algorithm
We now have enough information to visualize our algorithm.
Initialize two pointers left = 0 and right = len(nums) - 1 as the boundaries of our search space.
Now we iteratively try to reduce our search space until its either empty or we find the target.
- Initialize pointer mid = (left + right) // 2, and check if nums[mid] == target. If we find the target, we return mid. If it isn't, this removes mid from our search space.
Determine which half is sorted: check if nums[left] < nums[mid]. If true, the left half is sorted. If not, the right half is sorted.
In this case, the left half is sorted, so we check if the target is within nums[left] (8) and nums[mid] (16).
3 is not within 8 and 16, so we discard the left half of the array from our search space by updating left = mid + 1. We just reduced our search space in half!
Now we repeat the process as above with the updated search space...
- Set mid = (left + right) // 2 and check if nums[mid] == target.
- Check which half is sorted: nums[left] (17) is greater than nums[mid] (1), so the right half is sorted.
- Check if the target is within nums[mid] (1) and nums[right] (3). It is, so we update left = mid + 1 to discard the left half of the array.
This continues until either we find the target or our search space is empty (left > right).
Solution
Solution
def search(nums, target):left = 0right = len(nums) - 1while left <= right:mid = (left + right) // 2if nums[mid] == target:return midif nums[left] <= nums[mid]:# left half is sortedif nums[left] <= target and target < nums[mid]:# target is in the left halfright = mid - 1else:# target is in the right halfleft = mid + 1else:# right half is sortedif nums[mid] < target and target <= nums[right]:# target is in the right halfleft = mid + 1else:# target is in the left halfright = mid - 1return -1
Visualization
Try these examples:
def search(nums, target):left = 0right = len(nums) - 1while left <= right:mid = (left + right) // 2if nums[mid] == target:return midif nums[left] <= nums[mid]:if nums[left] <= target and target < nums[mid]:right = mid - 1else:left = mid + 1else:if nums[mid] < target and target <= nums[right]:left = mid + 1else:right = mid - 1return -1
search for 3 in rotated sorted array
0 / 9
Test Your Knowledge
Login to take the complexity quiz and track your progress
Complexity Analysis
Time Complexity: O(log n) where n is the number of elements in the array. We are reducing the search space by half in each iteration, just like we do in classic binary search.
Space Complexity: O(1) We are using a constant amount of space.
Mark as read
Your account is free and you can post anonymously if you choose.