import java.util.*;

class Find8 
// Binary search of an array (iterative) (timed, no display)
{
 public static void main(String[] args) throws Exception
 {
  Random rand = new Random();
  boolean b;
  long time1,time2;
  Scanner input = new Scanner(System.in);
  System.out.print("Enter the number of numbers: ");
  int num = input.nextInt();
  System.out.print("Enter the highest number: ");
  int high = input.nextInt();
  Integer[] a = new Integer[num];
  for(int i=0; i<num; i++)
      a[i]=rand.nextInt(high);
  Arrays.sort(a);
  System.out.print("Enter a number to search for: ");
  int n = input.nextInt();
  time1 = new Date().getTime();
  b = search(a,n);
  time2 = new Date().getTime();
  System.out.println("Time taken to search: "+(time2-time1)+"ms");
  if(b)
      System.out.println(n+" is in the array");
  else
      System.out.println(n+" is NOT in the array");
 }

 public static boolean search(Integer[] a,Integer n)
 {
  int from=0, to=a.length;
  while(from!=to)
     {
      int mid= (from+to)/2;
      int res = n.compareTo(a[mid]);
      if(res==0)
         return true;
      else if(res<0)
         to=mid;
      else
         from=mid+1;
     }
  return false;
 }

}