Search in Rotated Sorted Array

Try to solve the Search in Rotated Sorted Array problem.

We'll cover the following

Statement#

Given a sorted integer array, nums, and an integer value, target, the array is rotated by some arbitrary number. Search and return the index of target in this array. If the target does not exist, return -1.

An original sorted array before rotation is given below:

g array 1 10 20 47 59 63 75 88 99 107 120 133 155 162 176 188 199 200 210 222

After rotating this array 6 times, it changes to:

g array 176 188 199 200 210 222 1 10 20 47 59 63 75 88 99 107 120 133 155 162

Constraints

  • All values in nums are unique.
  • The values in nums are sorted in ascending order.
  • The array may have been rotated by some arbitrary number.
  • 1≤1 \leq nums.length ≤1000\leq 1000
  • −104≤-10^4 \leq nums[i] ≤104\leq 10^4
  • −104≤-10^4 \leq target ≤104\leq 10^4

Examples#

Created with Fabric.js 3.6.6 Input Output Index = 3 Sample example 1 target = 2 nums 6 7 1 2 3 4 5

1 of 3

Created with Fabric.js 3.6.6 Input Output nums 176 188 199 200 1 2 3 Sample example 2 Index = 2 target = 199

2 of 3

Created with Fabric.js 3.6.6 Input nums 1 2 3 4 5 6 7 Output Sample example 3 Index = -1 target = 8

3 of 3

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

1

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

A)

0

B)

1

C)

5

D)

6

Question 1 of 30 attempted

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.

Drag and drop the cards to rearrange them in the correct sequence

Declare two low and high pointers that will initially point to the first and last indexes of the array, respectively.

Declare a middle pointer that will initially point to the middle index of the array. This divides the array into two halves.

Check if the target is present at the position of the middle pointer. If it is, return its index.

If the first half of the array is sorted and the target lies in this range, update the high pointer to the middle pointer in order to search in the first half.

Else, if the second half of the array is sorted and the target lies in this range, update the low pointer to mid in order to search in the second half.

If the low pointer becomes greater than the high pointer and we still haven’t found the target, return −1-1.

Try it yourself#

Implement your solution in the following coding playground:

Python
usercode > main.py
Input #1
Input #2
%0 node_01 6 node_11 7 node_21 1 node_31 2 node_41 3 node_51 4 node_61 5
Visualization for Input #1
Search in Rotated Sorted Array

Solution: First Bad Version

Solution: Search in Rotated Sorted Array