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