题解 | #求平方根#

大多数人都说搜索范围应该是不大于x的一半。 但是我觉得这个范围是错误的， 应该根据2的n次方来降低维度。 比如算1518991037的时候，range is 32768, 65536， 即2^15~16 所以先算x是2的多少次方

        int count=0;
        do{
            k=k>>1;
            count++;
        }while(k>1);

然后算一下二分法的区间。

int begin = 2<<((count>>1)-1);
        int end = 2<<(count>>1);
         
        System.out.println("range is " + begin + ", " + end);

我感觉搜索1518991037的一半二分， 相比（32768, 65536）二分，效能应该有点区别... 奈何程序计算告诉我速度没有其他人快。。。想不明白啊！！

其他二分法的地方就差不对了。 讨厌的地方时二分法的边界问题，特此需要判断指针重合的情况

   public int bincalc(int left, int right, int target){
        if(left==right){
            return left;
        }else if(left+1==right){
            if(right*right<target){
                return right;
            }else{
                return left;
            }
        }

具体上代码

import java.util.*;


public class Solution {
    /**
     * 
     * @param x int整型 
     * @return int整型
     */
    
    
    public int sqrt (int x) {
        // write code here
        int k = x;
        int count=0;
        do{
            k=k>>1;
            count++;
        }while(k>1);
        
        int begin = 2<<((count>>1)-1);
        int end = 2<<(count>>1);
        
        System.out.println("range is " + begin + ", " + end);
        return bincalc(begin, end, x);
        
    }
    
    public int bincalc(int left, int right, int target){
        if(left==right){
            return left;
        }else if(left+1==right){
            if(right*right<target){
                return right;
            }else{
                return left;
            }
        }
        int mid = left + ((right-left)>>1);
        if(mid*mid-target>0){
            return bincalc(left, mid-1, target);
        }else if(mid*mid-target<0){
            return bincalc(mid, right, target);
        }else{
            return mid;
        }
        
    }
}