public class BinSearch {

  /* Binary search:
   * =Return the value i such that a[i]<=z<a[i+1], array a is sorted in non-decreasing order.
   * If z is not in array a, a warning message will display and the returned value indicates
   *   the position after which z may be inserted in the sorted array a.  A return value -1
   *   is not a valid index but indicates that z<a[0].
   */
  public static int binarySearch(int[] a, int z) {
    // [L,R] is the search window, initialized to include "index" -1 and n
    // since z may not be in array a
    int L= -1;  
    int R= a.length;
    
    // Keep halving [L,R] until R=L+1 such that  a[L] <= z < a[R]
    while ( R != L+1 ) {
      int m= (L+R)/2;  //middle of search window, note integer division
      if ( a[m] <= z )
        L= m;
      else
        R= m;
    }
    
    if (L == -1 || z!=a[L])
      System.out.println("Warning: z="+z+" was not found in the array.");
    
    return L;
    
  }//method binarySearch
    

  // A small test of the binarySearch method
  public static void main(String[] args) {
    int[] a = new int[] {-4, -2, 0, 5, 5, 5, 8, 9};
    int[] target = new int[] {-2, 5, -4, 9, 4, -6, 11};
    
    System.out.println("Target    Returned value");
    System.out.println("------------------------");
    
    for (int i=0; i<target.length; i++){
      int pos = binarySearch(a, target[i]);
      System.out.printf("%4d %10d\n", target[i], pos);
    }
  }
}