6

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;
}
Improve this question
2
  • 1
    I think its essential. can you give the full problem description? Commented Apr 26, 2016 at 7:39
  • @AbuHanifa, thanks for asking and vote up, do you mean problem statement part? It is the complete statement. Which parts you are confused? I am happy to clarify. Commented Apr 26, 2016 at 20:08

2 Answers 2

Reset to default
3

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

12 Comments

Yeah...even if the array is rotated n times, if a[mid] == a[left], it is an implicit conclusion that either mid = left or all elements in the left half are equal. So, you can just check for the element in the right half.
@LinMa, also, I would suggest you make a generic implementation of Binary Search, so that you just have to write the condition function everytime, and not the whole binary search.
Ok...A further thought into this...I have made an edit to the answer. (Previous conclusion was wrong)
@LinMa, my Edit-2 in the answer answers your questions...does it not?
Thanks vish4071, you are correct. I missed Edit-2 and only see first edit. Mark your reply as an answer. :)
|
1

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

Improve this answer

16 Comments

@LinMa my idea is to simplify the problem into 2 problems, one of them is binary-search which is already you have the solution to. instead of trying to come up with a complex algorithm to solve the problem as a whole.
@LinMa my implementation of find_first_index gives O(n) which makes search gives O(n + log n). it can be re-implemented in a way that makes it O(log n) to make search have O(2 log n) ~ O(log n). but the idea remain the same.
@LinMa let's say it's rotated somewhere in the middle, you can instead of binary-search over the whole list, you binary-search one of the two halves based on comparison with the first and last item. so if key => a[0] search the right half, if key <= a[size-1] search the left half, else not-found.
@LinMa yes, and there is a way to find the mid-point in O(log n) I'll add it in when I've time.
@LinMa a[left] == a[mid] and a[mid] == a[right] would happen in one case, if the array have identical items like { 2, 2, 2, .. 2 .. 2, 2, 2 }
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.