Search in Rotated Sorted Array
Explore how to apply a modified binary search technique to locate a target value within a rotated sorted integer array. Understand the problem constraints such as unique elements and arbitrary rotations, and learn to implement an efficient search solution with a clear step-by-step process.
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:
int BinarySearchRotated(vector<int>& nums, int target){// your code will replace this placeholder return statementreturn -1;}