CODEWITHSUNDEEP
algorithm
dojoBeginner
dojoBeginner

Reputation: 449

searching a element in a array which is rotated N times

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?

Upvotes: 3

Views: 1962

Answers (3)

Terminal
Terminal

Reputation: 1999

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);
    }
}

Upvotes: 2

BiGYaN
BiGYaN

Reputation: 7179

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

Upvotes: 0

Christian
Christian

Reputation: 4375

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.

Upvotes: 0

Related Questions