What is the minimum of the absolute values of a sorted array of integers?
int[] ia = {-38, -20, -10, -5, -2, 3, 4, 5 }; the answer is 2.
The code is based on a slight twist to binary search.
public class MinAbs {
public int cal(int[] a ){
return recurscal( a, 0, a.length - 1);
}
private int recurscal(int[] a, int begin, int end){
assert (end >= begin);
if (end == begin) return Math.abs(a[begin]);
if ((end - begin) == 1)
return Math.min(Math.abs(a[begin]), Math.abs(a[end]));
final int middle = begin + (end - begin)/2;
// on downward slope, the new interval is middle to end
if ( (Math.abs(a[middle - 1] ) >= Math.abs(a[middle]))
&& (Math.abs(a[middle + 1] ) <= Math.abs(a[middle]))
) return recurscal(a, middle, end);
// on upward slope, the new interval is begin to middle.
if ( (Math.abs(a[middle - 1] ) <= Math.abs(a[middle]))
&& (Math.abs(a[middle + 1] ) >= Math.abs(a[middle]))
)return recurscal(a, begin, middle);
// No more testing. Middle is the answer.
return Math.abs(a[middle]);
}
public static void main(String[] args) {
int[] ia = {-38, -20, -10, -5, -2, 3, 4, 5 };
MinAbs mia = new MinAbs();
System.out.println(mia.cal(ia));
}
}
int[] ia = {-38, -20, -10, -5, -2, 3, 4, 5 }; the answer is 2.
The code is based on a slight twist to binary search.
public class MinAbs {
public int cal(int[] a ){
return recurscal( a, 0, a.length - 1);
}
private int recurscal(int[] a, int begin, int end){
assert (end >= begin);
if (end == begin) return Math.abs(a[begin]);
if ((end - begin) == 1)
return Math.min(Math.abs(a[begin]), Math.abs(a[end]));
final int middle = begin + (end - begin)/2;
// on downward slope, the new interval is middle to end
if ( (Math.abs(a[middle - 1] ) >= Math.abs(a[middle]))
&& (Math.abs(a[middle + 1] ) <= Math.abs(a[middle]))
) return recurscal(a, middle, end);
// on upward slope, the new interval is begin to middle.
if ( (Math.abs(a[middle - 1] ) <= Math.abs(a[middle]))
&& (Math.abs(a[middle + 1] ) >= Math.abs(a[middle]))
)return recurscal(a, begin, middle);
// No more testing. Middle is the answer.
return Math.abs(a[middle]);
}
public static void main(String[] args) {
int[] ia = {-38, -20, -10, -5, -2, 3, 4, 5 };
MinAbs mia = new MinAbs();
System.out.println(mia.cal(ia));
}
}
(0) Please include link to why l + (h-1)/2 is better.
ReplyDelete(1) Mention more about handling degenerate cases. Is it worth handling them upfront?
(2) Please speak to how binary search can be used as a black box if we could track the last index evaluated. We could search for 0 get the index and then evaluate the surrounding values.
(3) It would also be great to see a proof that the last index evaluated by BS is the closest to the query value.
(4) Finally, would love to see a post on in-place quick sort.