Coderust: Hacking the Coding Interview/

...

/

Search a Rotated Array

Search a Rotated Array

Search for a given number in a sorted array that has been rotated by some arbitrary number.

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 ...