Sunday, December 22, 2013

Find a number from sorted list where start and end of list is not known

Prob: find a number from a sorted list where start and end of list is not known. The moving pointer will rotate over from max to min and vice versa.

public class FindANumber {

    public int bTreeRotated(int A[], int start, int finish, int data) {
        int mid = start + (finish - start) / 2;
        if (start > finish) {
            return -1;
        }
        if (A[mid] == data) {
            return mid;
        } else if (A[start] <= A[mid]) {
            if (data >= A[start] && data <= A[mid]) {
                return bTreeRotated(A, start, mid - 1, data);
            } else {
                return bTreeRotated(A, mid + 1, finish, data);
            }
        } else //if(A[mid] <= A[finish]){
        if (data >= A[mid] && data <= A[finish]) {
            return bTreeRotated(A, mid + 1, finish, data);
        } else {
            return bTreeRotated(A, start, mid - 1, data);
        }
    }
 
    public static void main(String args[]){
        FindANumber fan = new FindANumber();
        int A[] = new int[]{15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14};
        int res = fan.bTreeRotated(A, 0, 11, 5);
        if(res < 0)
            System.out.println("Not Found!!");
        else
            System.out.println("Fund at " + res);
     
    }
}

No comments:

Post a Comment