/*
We wrote an iterative version of the binary search (see your notes or the text books if you don't remember the details). You can also perform a binary search on a sorted list recursively as follows:
   1. look in the middle.
   2. If that's the data item you're looking for you're done.
   3. If the item is possible in the upper half, recursively search in the upper half.
   4. If not, recursively search in the lower half. 

You don't want to continually split up and copy the lists, so you'd probably have a function header like the followingL:
   Object recursiveSearch(ArrayList l, Comparable whatImLookingFor, int lowIndex, int highIndex) 
    1. Implements a recursive binary search on an array of ints.
    2. Implements a recursive binary search on an ArrayList of comparable data objects.
    3. Your main routine should test both of these searches. 
*/
import java.io.*;
import java.util.*;

public class binarySearch
{
  static int index=0;
  static Object recursiveSearch(ArrayList l,Comparable i,int lowIndex,int highIndex)
  {
    int median = (int) (highIndex-lowIndex)/2;
    
    if (i.compareTo(l.get(median)) == 0)
      index = index + median;
    if (lowIndex == highIndex)
      return "Not found";
    else
    {
      if (i.compareTo(l.get(median)) > 0)
      {
        recursiveSearch(l,i,median+1,highIndex);
        index = index + median;
      }
      else
        recursiveSearch(l,i,lowIndex,median-1);      
    } 
    return index; 
  }
  public static void main(String[] args)
  {
    ArrayList<Integer> l = new ArrayList();
    for (Integer i=1;i<11;i++)
    {
      l.add(i);
    }
    recursiveSearch(l,6,0,9);
  }
}