Binary Search in sorted and shifted (rotated) array

We know that Binary Search can be used to find an element in a sorted array of elements in O(log n) time. The algorithm is very versatile and with little modifications, it can be utilized in many more places for efficiency. Let us see one such problem.

Problem statement: You've been given an array that is sorted and then rotated by some unknown offset. For example, consider a sorted array arr[] = {1, 2, 3, 4, 5}. This array is now rotated, say twice, to the right such that arr[] = {4, 5, 1, 2, 3}. The offset of rotation is not known to you for a given array. Devise a way to find an element in the rotated array in O(log n) time.

Modified Binary Search approach: Now how efficiently can one search in this sorted + rotated array? The key is to find the offset position, i.e. the position at which array order is changed. For example, in the above array arr[], the offset position can be taken as index 1 (where element 5 is stored) because the very next element is the actual starting element of the sorted array, which is the smallest element. It can be seen that the array is divided into two sorted sub-arrays at the offset position.

So, if the offset is known to us, we can apply Binary Search in the two sorted sub-arrays one by one to find out the element in O(log n) time. Now all we have to worry about is finding the offset, and that too in O(log n) running time. This can be accomplished via a modified Binary Search, which considers the fact that the offset element is the only element in the array for which the very next element to it is smaller. By using this as a condition, we can find the offset.

Solution: Here is a C program which implements the above approach.

#include <stdio.h>

/* Function to find the offset position in O(log n) via modified Binary Search */
int findOffset(int *arr, int low, int high, int size)
{
    int mid;
    if (low <= high)
    {
        mid = low + ((high - low) / 2);

        if (arr[mid] > arr[mid+1])
            /* Offset position found at mid */
            return mid;
        else
        if (arr[mid] > arr[size-1])
            /* Offset may be on the right hand side, as arr[mid] is greater than the very last element in arr[] */
            return findOffset(arr, mid+1, high, size);
        else
            /* Offset may be on the left hand side */
            return findOffset(arr, low, mid-1, size);
    }

    return -1;    // No offset found in arr[]
}

/* Function for performing Binary Search to find item in the array */
int binarySearch(int *arr, int low, int high, int item)
{
    int mid;
    if (low <= high)
    {
        mid = low + ((high - low) / 2);

        if (arr[mid] == item)
            return mid;
        else
        if (arr[mid] > item)
            return binarySearch(arr, low, mid-1, item);
        else
            return binarySearch(arr, mid+1, high, item);
    }

    return -1;
}

/* Main function */
int main()
{
    int i, size, offset, item, index, *arr;
    printf("\nEnter size of array: \n");
    scanf("%d", &size);
    arr = (int*)malloc(size * sizeof(int));

    printf("\nEnter elements in array: \n");
    for (i = 0; i < size; i++)
        scanf("%d", &arr[i]);

    printf("\nEnter search item: \n");
    scanf("%d", &item);

    /* Get the position of offset (rotation) */
    offset = findOffset(arr, 0, size-1, size);

    /* If the array was not rotated, use normal Binary Search */
    if (offset == -1)
    {
        index = binarySearch(arr, 0, size-1, item);
        (index != -1) ? printf("Item found at index  %d.\n", index) : printf("Item not found.\n");
    }
    /* Otherwise the array was rotated, use Binary Search in left and right sub-arrays separately */
    else
    {
        /* Search in the sub-array till the offset position */
        index = binarySearch(arr, 0, offset, item);
        if (index != -1)
            printf("Item found at index  %d.\n", index);
        else
        {
            /* Search in the sub-array right of the offset position */
            index = binarySearch(arr, offset+1, size-1, item);
            (index != -1) ? printf("Item found at index  %d.\n", index) : printf("Item not found.\n");
        }
    }

    return 0;
}