L50BinarySearch.java

public class L50BinarySearch{

  public static void main(String[] args){
    //ADD CODE HERE TO TEST METHODS
  }
  public static boolean isPalindrome(String s){
    return isPalindrome(s, 0, s.length() - 1);
  }

  public static boolean isPalindrome(String s, int low, int high){
    if(high <= low)
      return true;
    else if (!s.substring(low,low+1).equals(s.substring(high,high+1)))
      return false;
    else
      return isPalindrome(s, low+1, high-1);
  }

  public static int binarySearch(int a[], int key){
    int lb = 0;
    int ub = a.length - 1;
    while(lb <= ub){
      int m = (lb + ub)/2; //set a midpoint
      if(a[m] == key){
        return m;
      }
      else if (key > a[m]){
        lb = m + 1;   //set a new lowerbound
      }
      else{
        ub = m - 1;   //set a new upper bound
      }
    }
    return -1;     //key not found
  }

  private static int binarySearch(int a[], int key, int lb, int ub){
    if(lb > ub){
      return -1; //1. Begin by bailing out
    }
    else{
      int m = (lb + ub)/2;
      if(a[m] == key){
        return m; //2. Process the first
      }
      else if (key > a[m]){
        return binarySearch(a, key, m + 1, ub);  //3. Process
      }        //    the
      else{        //    rest
        return binarySearch(a, key, lb, m - 1);
      }
    }
  }

  public static int linearSearch(int[] a, int key){
    for(int i = 0; i < a.length; i++){
      if( a[i] == key ){
        return i;
      }
    }
    return -1;
  }
}