int binarySearch(int sortedArray[], int key) {
        int first = 0;
        int last = sortedArray.length - 1;
        
        while (first <= last) {
            int mid = (first + last) / 2;  // compute mid point.
            if (key > sortedArray[mid]) 
                first = mid + 1;  // repeat search in top half.
            else if (key < sortedArray[mid]) 
                last = mid - 1; // repeat search in bottom half.
            else
                return mid;     // found it. return position /////
        }
        return -1;    // failed to find key
     }

int rBinarySearch(int sortedArray[], int first, int last, int key) {
        
        if (first <= last) {
            int mid = (first + last) / 2;  // compute mid point.
            if (key == sortedArray[mid]) 
                return mid;   // found it.
            else if (key < sortedArray[mid]) 
                return rBinarySearch(sortedArray, first, mid-1, key);
            else
                return rBinarySearch(sortedArray, mid+1, last, key);
        }
        return -1;    // failed to find key
     }


TreeNode TreeSearch(TreeNode root, Object target)
{
        boolean found = false;

        while (root != null && !found)
           if (target < root.data)
                root = root.left;
           else if (target > root.data)
                     root = root.right;
           else found = true;
        return root;
}

TreeNode TreeSearch(TreeNode root, Object target)
{
      if (root)
           if (target < root.data)
                 root = TreeSearch(root.left, target);
           else if (target > root.data)
                 root = TreeSearch(root->right, target);
      return root;
}

class ReverseString
{
   public static void main(String [] args)
   {
      reverse("This is a plan.");
      System.out.println();
      reverse("This is a plan.", 0);
      System.out.println();
   }

   public static void reverse(String s)
   {
      for (int i = s.length() - 1; i >= 0; i--)
         System.out.print(s.charAt(i));
   }

   public static void reverse(String s, int position)
   {
      if (position == s.length())
         return;
      reverse(s, position + 1);
      System.out.print(s.charAt(position));
   }
}

class Fibonacci
{
   public static void main(String [] args)
   {
      System.out.println(System.currentTimeMillis());
      System.out.println(fibonacciNonRecursive(10));
      System.out.println(System.currentTimeMillis());
      System.out.println(fibonacciRecursive(10));
      System.out.println(System.currentTimeMillis());
   }

   static int fibonacciNonRecursive(int number)
   {
      switch (number)
      { 
         case 0 :
         case 1 : return 1;
         default :
            int current = 2, oneBack = 1, twoBack = 1;
            for (int i = 2; i <= number; i++)
            {
               current = oneBack + twoBack;
               twoBack = oneBack;
               oneBack = current;
            }
            return current;
      }
      
   }

   static int fibonacciRecursive(int number)
   { 
      switch (number)
      { 
         case 0 :
         case 1 : return 1;
         default :return (fibonacciRecursive(number-1) + 
                       fibonacciRecursive(number-2));
      }
   }
}