二分查找(一)——纯粹的二分查找

2018-09-24  本文已影响0人  旺叔叔

LeetCode_35_SearchInsertPosition

题目分析:

找大于target的最小数的下标。

解法一:递归

public static int searchInsert(int[] nums, int target) {
    return binarySearch(0, nums.length, nums, target);
}

//左闭右闭[begin,mid] 递归
public static int binarySearch(int begin, int end, int[] list, int target){
    if(begin == end)
        return begin;

    int mid = begin + (end - begin) / 2;//防溢出

    if (target < list[mid])
        return binarySearch(begin, mid, list, target);
    else if(target > list[mid])
        return binarySearch(mid + 1, end, list, target);
    else
        return mid;//题目说明无重复 相等直接剪枝
}

解法二:循环

//左闭右闭[begin,mid] 循环
public static int searchInsert2(int[] nums, int target) {
    int begin = 0, end = nums.length;
    while(begin != end){
        int mid = begin + (end - begin) / 2;//防溢出
        if(target < nums[mid])
            end = mid;
        else if(target > nums[mid])
            begin = mid + 1;
        else
            return mid;//题目说明无重复 相等直接剪枝
    }
    return begin;
}

细节分析:

解法一二只是形式不同,就以解法二为准,分析几个细节。
1.mid = begin + (end - begin) / 2 有两个注意点
  1)不能写成 mid = (begin + end) / 2 否则begin + end可能溢出
  2)在迭代过程中,规模缩减到end - begin = 1的时候  mid计算出的结果是等于begin的。
2.begin = mid + 1 而不是begin = mid
    因为细节1中的第2点,可看出 如果begin = mid 可能会出现死循环。
3.end = mid 而不是 end = mid - 1
    同样因为细节1中的第2点,end = mid就足以让搜索往左也不会出现死循环。
    mid - 1还会带来的问题,试试这个输入[1,3] target = 2
4.end = nums.length 而不是end = nums.length - 1
    因为taget大于所有值,需要返回数组最后一个位置nums.length

一句话总结这个写法:查找[begin,end]闭区间范围内的符合条件下标。

PS:之前看网上的无符号右移写法mid = (begin + end) >>> 2;后来亲测 2 >>> 2 == 0。与预期1不符。
上一篇下一篇

猜你喜欢

热点阅读