二分查找法做后总结

在二分查找中while中的判定范围

会有两种判定的方式，一种是左右都是闭合的，一种的左闭右开的。

1. 左右闭合

当左右都是选择闭合的时候，在while中要选择<=符号，并且在middle判断了之后，对left是+1，对right是-1

while(left<=right){
            middle=(left+right)/2;
            if(nums[middle]==target){
                key=middle;
                return key;
            }else if(nums[middle]<target){
                left=middle+1;
            }else{
                right=middle-1;
            }
        }
           

2. 左闭右合

在选择左闭右合的时候，在while中要选择<符号，并且在middle判断了之后，right直接等于middle即可，left要+1

while (left < right) {
       middle=(left+right)/2;
       if (nums[middle] > target) {
           right = middle; 
        } else if (nums[middle] < target) {
            left = middle + 1; 
        } else { // nums[middle] == target
            return middle;
        }
  }
           

3. 当找不到target并且要返回插入的位置时

我喜欢用左右闭合的方式写题目，所以当最后退出while循环的时候，left指向的位置就是要插入的位置

4. 用牛顿迭代法去写求x的平方根的整数部分

int mySqrt(int a) {
        long x = a;
        while (x * x > a){
         x = (x + a / x) / 2;
        }
        return (int)x;
    }