/***** BINARY SEARCH *******************************************\

This program demonstrates a simple BINARY SEARCH.
This can only function if the numbers in the array are SORTED,
from smallest to largest (Ascending order).

\***************************************************************/

   void setup()
   {
      double[] prices = {1.50,1.60,1.80,2.25,2.50,3.00};
      double find = inputDouble("Type the price you wish to find");
      int position = binarySearch(find,prices);
      if(position>=0)
      { output("Found in position " + position); }
      else
      { output("Not found"); }
   }
 
   public int binarySearch(double target, double[] nums)
   {
      //  An iterative binary search. 
      //  If found, returns position.  Else returns -1.

      int middle, low, high;
      boolean found = false;
      int size = nums.length;

      low = 0;
      high = size-1;
      middle = -1;

      while (high >= low && !found)
      {  middle = (low + high) / 2;
         if (target < nums[middle])
         {  high = middle - 1; }
         else if (target > nums[middle])
         {  low = middle + 1;  }
         else
         {  found = true;  }
      }

      if (found)
      {  return middle; }
      else
      {  return -1;  }
   }
  
   public void output(String message)
   {  javax.swing.JOptionPane.showMessageDialog(this,message);  }  

   public void output(int info)
   {  output(info + ""); }
  
   public String input(String prompt)
   {  return javax.swing.JOptionPane.showInputDialog(this,prompt);  }
  
   public double inputDouble(String prompt)
   {  double result=0;
      try{result=Double.valueOf(
                          input(prompt).trim()).doubleValue();}
      catch (Exception e){result = 0;}
      return result;
   }  
  
/**********************************************************\

(1) Try searching for the first number in the list,
    for the last number in the list, and for 2 numbers
    somewhere in the middle of the list.
   
(2) Add 4 more numbers. Again, try searching for various numbers,
    to make sure your method works correctly.

(3) Change the program so that it can do a binary search
    when the list of numbers is in DESCENDING order -
    from largest to smallest.
   
(4) Scramble up the array so the numbers are NOT in order.
    Now try doing a binary search.  Does it ALWAYS fail,
    or does it succeed sometimes?
   
(5) What happens if the array has only 1 single number in it?
    What if the array has NO numbers in it?   

\**********************************************************/