Search in Rotated Sorted Array
Understand how to locate an element in a rotated sorted array by applying a modified binary search. This lesson teaches you to handle rotation scenarios and solve problems with unique integer values, improving your algorithmic problem-solving skills.
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:
export function binarySearchRotated(nums, target) {// Your code here would replace the placeholder return statement.return -1;}