Main.java

class Main {
  public static void main(String[] args) {
    System.out.println("expect: 5");
    System.out.println("got: "+sqrt(25));
    System.out.println("expect: -1");
    System.out.println("got: "+sqrt(-1));
    System.out.println("expect: 0");
    System.out.println("got: "+sqrt(0));
    System.out.println("expect: 1");
    System.out.println("got: "+sqrt(1));
    System.out.println("expect: -1");
    System.out.println("got: "+sqrt(2));
    System.out.println("expect: -1");
    System.out.println("got: "+sqrt(26));
    System.out.println("expect: 100");
    System.out.println("got: "+sqrt(10000));
    System.out.println("expect: -1");
    System.out.println("got: "+sqrt(10001));
    //System.out.println("expect: 10000");
    //System.out.println("got: "+sqrt(100000000));
  }

  static int sqrt(int n){
    // return -1, if not found
    if(n<0){
      return -1;
    }
    if(n==0){
      return 0;
    }
    return sqrt_rc(n, 1, n);
  }

  static int sqrt_rc(int n, int left, int right){
    int middle = (left+right)/2;
    if(left == right){
      if(middle*middle == n){
        return middle;
      }else{
        return -1;
      }
    }
    if(middle*middle == n){
      return middle;
    }else if(middle*middle > n){
      return sqrt_rc(n, left, middle-1);
    }else{
      return sqrt_rc(n, middle+1, right);
    }
  }
}