// ---------------------------------------------------------------------------
// BinarySearch.java
//
// A simple implementation of binary search for Java
//
// Paul McNamee
// Introduction to Java Programming, 605.201, 8/97
// ---------------------------------------------------------------------------

// ---------------------------------------------------------------------------
// Binary search is an algorithm for searching ordered sets that can
// "find" in O(lg N), time logrithmic to the cardinality of the set
// instead of the O(N), linear time required if every element in the
// set is compared.

public class BinarySearch {
  public static void main (String [] args) {
    int primes[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 27};

    int x = Find(95, primes);
    System.out.println("Finding 95, result is " + x);

    x = Find(3, primes);
    System.out.println("Finding 3, result is " + x);
  }

  // Find x in the array, or return -1 for failure!  Call the
  // other Find function for results
  static int Find (int x, int [] array) {
    return Find(x, array, 0, array.length-1);
  }

  // The Binary search function (Note the use of recursion)
  static int Find (int x, int [] arr, int lo, int hi) {
    System.out.println("In Find, lo is " + lo + " and hi is " + hi); 
    if (arr[lo] == x) {
      return lo;
    } else if (arr[hi] == x) {
      return hi;
    } else if (hi <= lo+1) {
      return -1;  // couldn't find it
    } else {
      int mid = (int) ((hi+lo)/2);
      int result;
      if (x < arr[mid])
        result = Find(x, arr, lo, mid);
      else
        result = Find(x, arr, mid, hi);
      return result;
    }
  }
} 

// ---------------------------------------------------------------------------
// Some output:
// paulmac@nautilus: javac BinarySearch.java
// paulmac@nautilus: java BinarySearch
// In Find, lo is 0 and hi is 9
// In Find, lo is 4 and hi is 9
// In Find, lo is 6 and hi is 9
// In Find, lo is 7 and hi is 9
// In Find, lo is 8 and hi is 9
// Finding 95, result is -1
// In Find, lo is 0 and hi is 9
// In Find, lo is 0 and hi is 4
// In Find, lo is 0 and hi is 2
// In Find, lo is 1 and hi is 2
// Finding 3, result is 1
// paulmac@nautilus: