import java.util.Scanner;

/* Binary Search */
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
  
  /* 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].
   * This version explicitly checks for z at a[(L+R)/2].
   */
   public static int binarySearch2 (int[] a, int z) {  
   
    int L =-1, R = a.length; // initial values for the search window
    
    while ( z!= a[(L+R)/2] && L+1!=R ) { 
      int m = (L+R)/2; 
      if (z>= a[m]) // z is to the left of the midpoint
        L = m;   
      else // z is to the right of the midpoint 
        R = m;  
    }  

    if (z==a[(L+R)/2]) 
      return (L+R)/2; 
    else { 
      System.out.println("Warning2: z="+z+" was not found in the array.");
      return L;
    }
  } 
 
 
 
  /* Test the binary search method
   */
    
  public static final int SIZEOFARRAY = 30; 
  public static final int RANGE = 10; 
  
  public static void main(String[] args) { 
     int[] a = new int[SIZEOFARRAY]; 
     
     System.out.print("The following are the contents of array a : \n");   
     a[0] = (int)(RANGE*Math.random());  
     System.out.printf("a[%d]= %d,\n",0, a[0]);    
     // What does the following loop do? 
     // it generates an increasing sequence of numbers to store in a
     // and displays each number as it is generated, without line breaks
     for (int j=1; j<SIZEOFARRAY; j++) {
       a[j] = a[j-1] + (int)(RANGE*Math.random()); 
       System.out.printf("a[%d]= %d,\t",j, a[j]);    
       if (j%5==0) System.out.printf("\n");    
     }
     System.out.println("\nWhich number do you want to search for? ");  
     Scanner keyboard = new Scanner(System.in); 
     int z = keyboard.nextInt();
     int i = binarySearch(a, z); 
     System.out.println("z ="+z+ " is at or should be inserted after position "+ i); 

    // Uncomment the following section to carry out an exhaustive test; 
    /*******************
      for (int k=1; k<SIZEOFARRAY; k++)  {

      // Use the following to look for z that ARE in a 
      //z=a[k];

      // Use the following set of lines to make z  random 
      z = (int)(RANGE*SIZEOFARRAY/2* Math.random());  

      int i1= binarySearch(a,z);
      int i2= binarySearch2(a,z);
      System.out.println("z=" + z + ".  Method1: z is at or should go afer " + i1 +
                         ".  Method2: z is at or should go afer " + i2 + ".");
    }
    *******************/
    
   } // main method 
} // BinSearch class