public class RecursiveBinarySearch {

	public static AddressEntry recSearch(AddressEntry[] addressBook,
	 String name) {
	   return recSearch(addressBook, name, 0, addressBook.length-1);
	}

	private static AddressEntry recSearch(AddressEntry[] addressBook,
	 String name, int first, int last) {
	   // base case: if the array section is empty, not found
	   if (first > last)
	      return null;
	   else {
	      int mid = (first + last) / 2;
	      // if we found the value, we're done
	      if (name.equalsIgnoreCase(addressBook[mid].getName()))
	         return addressBook[mid];
	      else if (name.compareToIgnoreCase(
	        addressBook[mid].getName()) < 0) {
	          // if value is there at all, it's in the left half
	          return recSearch(addressBook, name, first, mid-1);
	      }
	       else { // array[mid] < value
	          // if value is there at all, it's in the right half
	          return recSearch(addressBook, name, mid+1, last);
	      }
	   }
	}

	public static void main(String[] args) {
	   // list must be in sorted order
	   AddressEntry addressBook[] = {
	      new AddressEntry("Audrey", "434-555-1215"),
	      new AddressEntry("Emily" , "434-555-1216"),
	      new AddressEntry("Jack"  , "434-555-1217"),
	      new AddressEntry("Jim"   , "434-555-2566"),
	      new AddressEntry("John"  , "434-555-2222"),
	      new AddressEntry("Lisa"  , "434-555-3415"),
	      new AddressEntry("Tom"   , "630-555-2121"),
	      new AddressEntry("Zach"  , "434-555-1218")
	   };
	   AddressEntry p;
	   // first element
	   p = recSearch(addressBook, "Audrey");
	   if (p != null) {
	      System.out.println("Audrey's telephone number is " + 
	       p.getNumber());
	   }
	   else {
	      System.out.println("No entry for Audrey");
	   }
	   // middle element
	   p = recSearch(addressBook, "Jim");
	   if (p != null) {
	      System.out.println("Jim's telephone number is " + 
	       p.getNumber());
	   }
	    else {
	       System.out.println("No entry for Jim");
	   }
	   // last element
	   p = recSearch(addressBook, "Zach");
	   if (p != null) {
	      System.out.println("Zach's telephone number is " + 
	       p.getNumber());
	   }
	   else {
	      System.out.println("No entry for Zach");
	   }
	   // non existent entry
	   p = recSearch(addressBook, "Frank");
	   if (p != null) {
	      System.out.println("Frank's telephone number is " + 
	       p.getNumber());
	   }
	   else {
	      System.out.println("No entry for Frank");
	   }
	}
}