Square root


 Implement a fast Integer square root function that takes
   in a 32-bit Integer and returns another 32-bit integer

   that is the floor of the square root of the input


In this problem i will solve this using binary search all i need to do is start from 0 to end 2^16

time complexity should be o(log n)




package Search;
/**
 * Implement a fasthteger square root functiOI1that takes
 *  in a 32-bit unsigned lteger and returns another 32-bit unsigned integer
 *  that is the floor of the square root of the input
 * @author Mohamed fawzy
 * @copyright GPL
 */
public class SquareSearch {

 public static  int SqrtSearch(int input){
  int begin = 0;
  int end   = 65536;
  while(begin+1 < end){
   int mid = begin + (end - begin) /2;
   int midSquare = mid * mid;
   if(midSquare == input){
    return mid;
   }else if(midSquare > input){
    end=mid;
   }else{
    begin=mid;
   }
  }
  return begin;
 }
}

Test case

package Search;

public class SquareSearchTest {
 
 public static void main(String[] args){
  SquareSearch squaresearch = new SquareSearch();
  System.out.println(squaresearch.SqrtSearch(32));
  System.out.println(squaresearch.SqrtSearch(5000));
  System.out.println(squaresearch.SqrtSearch(1024));
  System.out.println(squaresearch.SqrtSearch(2048));
  System.out.println(squaresearch.SqrtSearch(4096));


 }

}

Comments

Popular Posts