Search a Rotated Array
Search for a given number in a sorted array that has been rotated by some arbitrary number.
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:
After rotating this array 6 times, it changes to:
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 - Codereturn -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
...
Access this course and 1400+ top-rated courses and projects.