02-二分查找

定义：在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。

• 时间复杂度：二分算法的时间复杂度是对数级别的

%0A#card=math&code=O%28%5Clog%20n%29%0A&id=D566P)

• 空间复杂度：使用了常数个数的辅助空间用于存储和比较

%0A#card=math&code=O%281%29%0A&id=kPVUN)

除非输入数据量很少，否则二分查找算法比线性搜索更快，但数组必须事先被排序。

例题：

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

class Solution {
    public int mySqrt(int x) {
        if(x == 0) return 0;
        long left = 1;
        long right = x/2;
        while(left<right){
            long mid = (left+right)/2+1; //+1的原因
            if(mid>x/mid){
                right = mid-1; //-1的原因
            }
            else{
                left = mid;
            }
        }
        return (int)left;
    }
}