算法(六) 二分查找

最基本的算法，常用于比较目标值和数组中间元素。时间复杂度为O(logN)。

1，例题

1,二分查找

来自LeetCode704

最最简单的二分题了，，，，面试热度那么高闹哪样呢，，，，

解法

class Solution {
    public int search(int[] nums, int target) {
        int middle;
        int left = 0;
        int right = nums.length - 1;
        while(left<=right){
            middle = left + (right - left)/2;
            if(nums[middle] == target) 
                return middle;
            else if(nums[middle] < target){
                left = middle + 1;
            }
            else
                right = middle - 1;
        }
        return -1;
    }
}

务必注意二分式子，不可以(left+right)/2。

理解

1，二分式子不可以直接 middle = (left+right）/2，这样遇到nt测试用例，可能加起来会溢出。不过这个式子也并非原始式子。

原始式子应该是middle = left + (left – right)/2，这能体现中间值的过程，也能防止溢出问题。

2,x的平方根

来自LeetCode69

计算机的方法很简单
数学方法真特么难啊，还好没学数学（牛顿迭代法）

解法

class Solution {
    public int mySqrt(int x) {
        if(x==0||x==1)
            return x;
        int l = 0;
        int r = x;
        int res = -1;;
        while(l<=r){
            int middle = l + (r - l)/2;
            if(x/middle<middle){
                r = middle-1;
            }
            else if(x/middle>middle){
                l = middle+1;
                if(x/(middle+1)<(middle+1))
                    return middle;
            }
            else
                return middle;
        }
        return -1;
    }
}

务必注意二分式子，不可以(left+right)/2。

理解

1，有空可以学习一下这题的数学思想，牛顿迭代法。