/* Live coding from Lecture 08 on Recursion continued. */

class L08 {
  /** isPal(s) returns true iff s is a palindrome
    * Preconditions: true
    */
  public static boolean isPal(String s) {
    int n = s.length();
    // Base cases: s has length 0 or 1
    if (n == 0 || n == 1) return true;
    // s has length >= 2
    if (s.charAt(0) == s.charAt(n - 1)) 
      return isPal(s.substring(1, n-1));
    else 
      return false;
   }
  
   /** exp(a,n) returns a^n
     * Precondition: n >= 0
     */
  public static double exp(double a, int n) {
    if(n == 0) return 1;
    return a * exp(a, n-1);
  }

  /** fastExp(a,n) returns a^n
    * Precondition: n >= 0
    */
  public static double fastExp(double a, int n) {
    if(n == 0) return 1;
    if(n % 2 == 0) return fastExp(a * a, n / 2);
    return a * fastExp(a, n - 1);
  }
  
  /** search(a,k,fst,lst) returns an index i such that a[i] = k
    * Precondition: such an index exists and a is sorted in ascending order
    */
  public static int search(int[] a, int k, int fst, int lst) {
    if(fst == lst) return fst;
    int m = (fst + lst) / 2;
    if (k <= a[m]) 
        return search(a, k, fst, m);
    else
        return search(a, k, m+1, lst);
  }
  
    /** fastSearch(a,k,fst,lst) returns an index i such that a[i] = k
    * Precondition: such an index exists and a is sorted in ascending order
    */
  public static int fastSearch(int[] a, int k, int fst, int lst) {
    while(true) {
      if(fst == lst) return fst;
      int m = (fst + lst) / 2;
      if (k <= a[m]) 
        lst = m;
      else
        fst = m + 1;
    }
  }
  
  
  
  
  
  
  
  
  
}