/* Program that implements and test recursive binary search.
 *
 * Carsten Butz, September 2002
 */
class RecBinSearch{

  public static void main(String[] args){

    int[] arr = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};

    System.out.println("key = " + 0 + "\t\t" + recbinsearch(arr,0,0,arr.length-1));
    System.out.println("key = " + 4 + "\t\t" + recbinsearch(arr,4,0,arr.length-1));
    System.out.println("key = " + 21 + "\t" + recbinsearch(arr,21,0,arr.length-1));
  }

  static boolean recbinsearch(int[] arr, int key, int l, int r){
    /* method that implements recursive binary search
     */ 
    int c;                  // centre point

    if(r<l)
      return false;
    else 
      {
	c = (l+r)/2;
	if(arr[c]==key)
	  return true;
	else if(arr[c]<key)
	{// search in upper part
	  return recbinsearch(arr, key, c+1, r);
	}
	else
	  {// search in lower part
	    return recbinsearch(arr, key, l, c-1);
	  }
      }
  } 

}