### Problem Statement

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

*(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2 ).*

You are given a target value to search. If found in the array, return its index, otherwise return `-1`

.

You may assume no duplicate exists in the array.

### Solution Approach

#### Linear Search

A linear solution would be to traverse the entire array and compare each element of the array with the given target value. Linear Search algorithm have **O(N)** time complexity.

let A = array let N = length of array let K = target value for i = 1 to N: if A[i] == K: print i

#### Binary Search

Binary Search takes **O(log(N))** time complexity to search an element inside the array. Since the array is rotated, we will have to use a modified version of binary search.

let’s declare some variables first.

let A = Array let N = length of Array let K = target value let low = 1 let high = N

The first thing we need to do is to divide the array in two sorted parts. There is a point in the array which divides the array called the pivot. The pivot element could either be the largest element of the array or the smallest as they appear side by side inside the rotated array.

We are gonna take pivot as the smallest element of the array. The idea is to check the middle element with the current pivot to determine the next subarray to chose from. Since we are looking for smallest element, we will use mid instead of mid-1 during left movements.

let pivot = 0; while(low < high) { let mid = low + (high-low)/2; if(A[mid] > A[pivot]) { low = mid+1; } else if(A[mid] < A[pivot]) { pivot = mid; high = mid; } else { low = mid+1; } }

Now that we have our pivot, we can use our simple binary search algorithm on the one of the subarrays divided by pivot based on whether the target value is smaller than the first element. In special case where the array is not rotated, our pivot would be 0 and binary search would be used on the entire array.

if(pivot == 0) { // no rotation low = 0; high = A.size()-1; } else { if(K < A[0]) { low = pivot; high = A.size()-1; } else { low = 0; high = pivot-1; } } while(low <= high) { let mid = low + (high-low)/2; if(A[mid] > K) { high = mid-1; } else if(A[mid] < K) { low = mid+1; } else { return mid; } }

Implementation in C++ is available at GitHub.