Given an array of positive and negative numbers sorted in ascending order.Find a number which is equal to the index of that number in array.
ex: Array = {-3,-1,0,1,4}
ans: a[4]=4
We can do it by linear search in O(n) time or by doing binary search in O(logN) time.
ex: Array = {-3,-1,0,1,4}
ans: a[4]=4
We can do it by linear search in O(n) time or by doing binary search in O(logN) time.
public class FixedPoint {
public static void main(String[] args) {
int[] a = { -10, -5, 0, 3, 7 };
int fixedPoint = getFixedPointNumber(a, 0, a.length - 1);
if (fixedPoint != -1) {
System.out.println("Number is : " + fixedPoint);
} else {
System.out.println("There is Number satisying the condition.");
}
}
/**
* Returns a number a[i] which satisfies the condition a[i]=i
*
* @param a
* @param low
* @param high
* @return
*/
private static int getFixedPointNumber(int[] a, int low, int high) {
if (a == null || a.length == 0 || low < 0 || high >= a.length
|| low > high)
return -1;
int mid = (low + high) / 2;
if (a[mid] == mid) {
return mid;
} else if (a[mid] < mid) {
return getFixedPointNumber(a, mid + 1, high);
} else {
return getFixedPointNumber(a, low, mid - 1);
}
}
}
No comments:
Post a Comment