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].

   */

  private static int binarySearch(int[] a, int z) {

    

    //Implement this method and change the dummy return statement below

    return -1;

    

  }

  

  

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

    }

  }

}