Search⌘ K
AI Features
Home
Courses
Coderust: Hacking the Coding Interview

Search a Rotated Array

Understand how to search for a target value in a rotated sorted array by applying modified binary search techniques. Explore both iterative and recursive solutions that maintain logarithmic time complexity and gain skills to handle rotated array search problems effectively.

We'll cover the following...

Statement

We’re given a sorted integer array, nums and an integer value, target. The array is rotated by some arbitrary number. Search the target in this array. If the target does not exist then return -1.

Example

An original array before rotation is given below:

g array 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 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 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 176 188 199 200 210 222 1 10 20 47 59 63 75 88 99 107 120 133 155 162

Our task is to find the target in an already rotated array.

Sample input

nums = [6, 7, 1, 2, 3, 4, 5]
target = 3

Expected output

4

Try it yourself

#include <iostream>
#include <vector>
using namespace std;
int BinarySearchRotated(vector<int>& nums, int target) {
	// TODO: Write - Your - Code
	return -1;
}

Solution 1: Iterative

The solution is essentially a binary search but with some modifications. When we look at the array in the example, you may notice that at least one-half of the array is always sorted. We can use this property to our advantage. If the target lies within the sorted half of the array, our problem is a basic binary search. Otherwise, discard the sorted half and keep examining the unsorted half. Since we partition the array in half at each step, this gives us ...