rotated ordered array search

Question

Working on below algorithm puzzle. Post problem statement and solution working on. The question is, whether we need "search both halves" part to keep it safe? Or when a[left] == a[mid], we can just search right part without checking whether a[mid] == a[right] -- since when a[left] == a[mid], I think all elements on the left are equal and cannot be satisfied with search condition to find value.

In more details, I mean whether it is safe to write last else if as,

else if (a[left] == a[mid]) {
            return search(a, mid + 1, right, x);
    }

Problem statement

Given a sorted array of n integers that has been rotated unknown number of times, write code to find an element in the array, you may assume that the array was originally sorted in increasing order

Example, Input find 5 in {15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14} Output, 8 (the index of 5 in the array)

Code

public static int search(int a[], int left, int right, int x) {
    int mid = (left + right) / 2;
    if (x == a[mid]) { // Found element
        return mid;
    }
    if (right < left) {
        return -1;
    }

    /* While there may be an inflection point due to the rotation, either the left or 
     * right half must be normally ordered.  We can look at the normally ordered half
     * to make a determination as to which half we should search. 
     */
    if (a[left] < a[mid]) { // Left is normally ordered.
        if (x >= a[left] && x < a[mid]) { 
            return search(a, left, mid - 1, x);
        } else {
            return search(a, mid + 1, right, x);
        }
    } else if (a[mid] < a[left]) { // Right is normally ordered.
        if (x > a[mid] && x <= a[right]) {
            return search(a, mid + 1, right, x);
        } else {
            return search(a, left, mid - 1, x);
        }               
    } else if (a[left] == a[mid]) { // Left is either all repeats OR loops around (with the right half being all dups)
        if (a[mid] != a[right]) { // If right half is different, search there
            return search(a, mid + 1, right, x);
        } else { // Else, we have to search both halves
            int result = search(a, left, mid - 1, x); 
            if (result == -1) {
                return search(a, mid + 1, right, x); 
            } else {
                return result;
            }
        }
    }
    return -1;
}

Answer 1

As far as your question is concerned, your assumption is totally correct that you don't have to search both halves there. You can just search the right half since if a[mid] != key, your element is surely in right half, if it is in the array that is.

EDIT:

The above conclusion is incomplete. I now write a new one with some further thought into this.

Firstly, if at any point of time, you are searching both halves, there is no point in doing Binary Search as the complexity of your search becomes O(n).

Now, you are right there that if a[mid] == a[left], your key can be in any of the halves. But, one thing you can be sure of, is that, one of the halves will have all elements equal.

eg. Suppose a[12] = [1,1,1,2,2,2,2,2,2,2,2,2]
    rotate r=2 times, a`[12] = [2,2,1,1,1,2,2,2,2,2,2,2]
    so, a[mid] = a[left] = 2
    if key = 1, it is in left half.

    now, rotate r=9 times,
         a``[12] = [2,2,2,2,2,2,2,2,2,1,1,1]
    so, a[mid] = a[left] = 2
    if key = 1, it is in right half

So, you need to search both halves of this array for your key, and this case actually makes Binary Search redundant.

So, now, I'd even propose you use the solution I mentioned below.

Though if there are no constraints, I'd like to propose a solution to it:

This is a simple variation to Binary Search algorithm.

You first have to apply Binary Search in the array, with the terminating condition:

a[mid-1] > a[mid]

Once this condition is met, you have the index k = mid, which gives you 2 sorted arrays.

First array, A[0...k-1] and second array, A[k...n-1], assuming n elements.

Now, just make a check.

if(key > A[0])
    Binary Search in A[0...k-1]
else
    Binary Search in A[k...n-1]

One exception, if array has been rotated n times, you won't get a value of k. Binary search the whole array for key.

EDIT2: Answering your questions from comments

I am wondering for my original method if a[left] < a[mid], and x >= a[left] && x < a[mid], if it safe to search only on left side using search(a, left, mid - 1, x);, if the array may be rotated n times?

If a[left] < a[mid], then we can be sure that a[left...mid] is ascending ordered (sorted). So, if x >= a[left] && x < a[mid], search only in left half is enough.

if you could also clarify when a[left] == a[mid], and a[mid] == a[right] , we need to search both directions?

Yes. In this case, we need to search both directions. Say, eg. your original array is {1,2,2,2,2,2,2,2,2,2} which is rotated once. Array becomes, {2,1,2,2,2,2,2,2,2,2}. If it is rotated 8 times, it becomes {2,2,2,2,2,2,2,2,1,2}. Now, if your search key is 1, right in the starting, in both cases, a[mid] == a[left] == a[right], and your key is in different halves. So, you need to search both halves for the key.

Answer 2

There are two things you need to take in consideration..

First since the array is rotated means it's like a circular buffer, so you need to access the array in a different way to avoid going off the array boundary.

Normal

    array[index]

Circular

    array[index % size]

Secondly you need to consider the rotation, the first ordered item is not index 0, let's say it's index f as first, so to access ordered index i, you use i+f.

Normal

    array[index]

Circular

    array[index % size]

Rotated

    array[(index + first) % size]

To find the first item of the rotated ordered array we can check where the sorting condition breaks..

// assuming ascending order a[0] <= a[1]

int find_first_index (int [] arr)
{
    for(int i = 0; i < arr.length; i++)
    {
        if(arr[i] > arr[(i+1) % arr.length])
        {
            return (i+1) % arr.length;
        }
    }

    return 0;
}

Now you just need to obtain that first index before sorting..

int f = find_first_index(arr);

Then replace all array access in the sorting algorithm with [(i+f) % arr.length] instead of arr[i]. So your code becomes like this..

public static int startSearch(int a[], int x)
{
    int f = find_first_index(a);
    return search(a, f, 0, (a.length-1), x);
}

public static int search(int a[], int f, int left, int right, int x)
{
    int s = a.length;
    int mid = (left + right) / 2;
    if (x == a[(mid+f)%s]) { // Found element
        return mid;
    }
    if (right < left) {
        return -1;
    }
..

.. The complete source-code is Here