Find an element in a rotated array

 

Griffith Observatory, Los Angeles, CA

An sorted array of integers was rotated an unknown number of times.

Given such an array, find the index of the element in the array in faster than linear time. If the element doesn't exist in the array, return null.

For example, given the array [13, 18, 25, 2, 8, 10] and the element 8, return 4 (the index of 8 in the array).

You can assume all the integers in the array are unique.

Understanding the Problem

In a rotated Array, elements are shifted right and the elements at the end of the array are inserted to the start of the array. The objective of the problem is

• Search for an element
• Return the original non rotated index of the element
• Do this in less than linear time

The original array is sorted in ascending order.

Initial Approach

We could just do one pass on the array to figure the locations of the element and the start of the array. We can then use these two pieces of information along with the size of the array to determine the non rotated index of the element

We can optimize by traversing the array towards the middle.

The approaches above are in linear time however, one ask of the problem is that we do this in less than linear time.

Binary Search

The binary search algorithm takes O(log n) runtime to search for an element in a sorted list.

The given problem consists of a rotated array. We can definitely say that the sub-array to the left and right of the point of rotation or pivot should be ordered. Therefore a binary search algorithm would perform on either of these sub-arrays if we knew the index of the pivot. The index of the pivot is also necessary in finding the non rotated index.

We can use a modified binary search in order to find the point of pivot. The modification is that we compare the neighbors of the middle element in a binary search and ascertain if either is the pivot point. We do this recursively on each sub-array until we find the pivot

https://www.geeksforgeeks.org/search-an-element-in-a-sorted-and-pivoted-array/

static int findPivot(int arr[], int low, int high)
{
    // base cases
    if (high < low)
        return -1;
    if (high == low)
        return low;

    /* low + (high - low)/2; */
    int mid = (low + high) / 2;
    if (mid < high && arr[mid] > arr[mid + 1])
        return mid;
    if (mid > low && arr[mid] < arr[mid - 1])
        return (mid - 1);
    if (arr[low] >= arr[mid])
        return findPivot(arr, low, mid - 1);
    return findPivot(arr, mid + 1, high);
}

Using this pivot point we establish the starting index of the non-rotated array, and can perform a binary search on the left and/or right side of the pivot in order to find the element we are searching for.