Wednesday, July 16, 2014

A discrete optimization problem

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

}

1 comment:

  1. (0) Please include link to why l + (h-1)/2 is better.
    (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.

    ReplyDelete