searching a element in a array which is rotated N times

Question

I have a sorted array which is rotated n times, n is unknown.Now I want to search an element using binary search in O(nlog n).I implemented the following code, it works fine. But I think condition if((end-start)==1 ) can be skipped by making some modifications, can any one suggest?

Eg of array 1 2 3 4 5 
            2 3 4 5 1 //rotated once

Code:

public static int srch(int a[],int start,int end,int key){
    if(start>end)
        return -1;

    if((end-start)==1 ){
        if(key==a[start])
            return start;
        else if(key==a[end])
            return end;
        else
            return -1;
    }
    int mid = (start+end)/2;

    if(a[mid]== key){
        return mid;
    }
    else{
        if(a[start] < a[mid] ){
            //first half is sorted
            if(key>a[mid]|| key <a[start]){
                start= mid+1;
            }else{
                end =mid-1;
            }
        }else{
            //second half is sorted

            if(key>a[mid]){
                start= mid+1;
            }else{
                end =mid-1;
            }
        }
        return srch(a, start, end, key);
    }
}

Any better/simple/more efficient solution?

possible duplicate of [Searching in an sorted and rotated array](http://stackoverflow.com/questions/4773807/searching-in-an-sorted-and-rotated-array) — codaddict, Jun 06 '11 at 09:57
You post seems to be Duplicate of : http://stackoverflow.com/questions/2834652/seaching-for-an-element-in-a-circular-sorted-array — Margus, Jun 05 '11 at 23:36

Terminal · Answer 1 · 2011-06-06T16:39:51.357

Your solution fails for array {4,5,1,2,3} and key=4. I think a modification in second part will solve the problem

else{
            //second half is sorted

            if(key>a[mid] && key<=a[end]){// modified condition
                start= mid+1;
            }else{
                end =mid-1;
            }

But I think condition if((end-start)==1 ) can be skipped by making some modifications, can any one suggest?

I suppose this condition is not required at all. Can u suggest a test case which fails for your modified code.

public static int srch(int a[],int start,int end,int key){
    if(start>end)
        return -1;

     int mid = (start+end)/2;

    if(a[mid]== key){
        return mid;
    }
    else{
        if(a[start] < a[mid] ){
            //first half is sorted
            if(key>a[mid]|| key <a[start]){
                start= mid+1;
            }else{
                end =mid-1;
            }
        }else{
            //second half is sorted

            if(key>a[mid] && key<=a[high]){
                start= mid+1;
            }else{
                end =mid-1;
            }
        }
        return srch(a, start, end, key);
    }
}

score 0 · Answer 2 · answered May 10 '11 at 06:47

Your solution is running in O(log n), so there cannot be a more efficient solution. Maybe parts of your code could be optimized, but that will not effect the running time in terms of O. As you said, the code works and returns the correct values, therefore I'd say it's the correct answer for your interview question.

score 0 · Answer 3 · answered May 15 '11 at 08:50

0

I haven't checked your code thoroughly for correctness, but your solution is O(log n). You cannot have a better solution algorithmically.

answered May 15 '11 at 08:50

BiGYaN

6,974
5
30
43

searching a element in a array which is rotated N times

3 Answers3