Search in Rotated Sorted Array
Understand how to search for a target value in a rotated sorted array by applying modified binary search strategies. This lesson helps you develop skills to identify the target index or determine if it is absent, using efficient and practical problem-solving approaches suitable for coding interviews.
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:
package mainfunc binarySearchRotated(nums []int, target int) int {// Replace this placeholder return statement with your codereturn -1}