算法(六) 二分查找

最基本的算法,常用于比较目标值和数组中间元素。时间复杂度为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,有空可以学习一下这题的数学思想,牛顿迭代法。

正文完