Search in Rotated Sorted Array
Explore how to identify the target element's index in a rotated sorted array by applying modified binary search methods. This lesson helps you understand key strategies for handling arrays rotated by arbitrary amounts and equips you with a clear approach to solve this common interview problem efficiently.
We'll cover the following...
Statement
You are given a sorted integer array, nums, and an integer, target. The array may have been rotated by an arbitrary number. Your task is to find and return the index of target in this array. If target does not exist, return -1.
An original sorted array before rotation is given below:
After rotating this array 6 times, it changes to:
Constraints
- All values in
numsare unique. - The values in
numsare sorted in ascending order. - The array may have been rotated by some arbitrary number.
-
nums.length -
nums[i] -
target
Examples
Understand the problem
Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps us to check if you’re solving the correct problem:
Search in Rotated Sorted Array
What is the output if the following rotated sorted array and target are given as input?
nums = [4, 5, 6, 7, 0, 1, 2]
target = 1
0
1
5
6
Figure it out!
We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.
Try it yourself
Implement your solution in the following coding playground:
def binary_search_rotated(nums, target):# Replace this placeholder return statement with your codereturn -1