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

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不符。