Geek asks and answers

Search for an element in an array that rotates N times

I have a sorted array that rotates n times, n is unknown. Now I want to search for an element using binary search in O (nlog n). I implemented the following code, it works great. But I think that the condition if ((end-start) == 1) can be skipped by making some changes, can anyone suggest?

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

the 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 / simpler / more efficient solution?

+3
source share
3 answers

Your solution is not suitable for the array {4,5,1,2,3} and key = 4. I think that the modification in the 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 that the condition if ((end-start) == 1) can be skipped by making some changes, can anyone suggest?

, . , .

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

O (log n), . , , O. , , , .

0

I have not fully verified your code for correctness, but your solution is O (log n). You cannot have a better solution algorithmically.

0
source

More articles:


All Articles