Rotated Sorted Array Search

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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s