二分法

适用范围

从已经排好顺序的数组当中找到目标所在位置或者是正确地向数组中插入一个目标。

思想

将整个数组不停地拆分为两段（每一段有左边界left和右边界right），用分隔两段的数（mid处值）与目标相比较，观察目标处于哪一段，最终段长小于2时，便可唯一确定位置，其时间复杂度为log₂n。

划分的具体过程

这里列出一种划分&确定边界&结束的方法，仅供参考。

如下列数组{1,2,4,8,16},target=11，查找其应该插入的位置，left意味着target至少应该从该位置插入

步骤	说明	a[0]	a[1]	a[2]	a[3]	a[4]	target
		1	2	4	8	16	11
0	left=0,right=4,mid=(left+right)/2=2	left		mid		right
1	因a[mid]=4<target left需右移至mid+1 故left=3,right=4,mid = (3+4)/2 = 3				left mid	right
2	a[mid]=8<target,left右移至4 mid = 4					left mid right
3	到这一步段距为1了，再做一下判断target<a[mid]=16,因此right=mid-1=3,至此，左边界超过了右边界，那么左边界就是我们需要查找的位置				right	left mid

存在问题

中值计算

mid = (left+right)/2在left和right值很大的时候可能造成数值溢出导致结果错误，因此可以换一种写法mid = left+(right-left)/2。

经过了解，还有另外一种写法就是mid = (left+right)>>>1,其中，>>>表示无符号右移运算符，其在右移时左边空位会补上0，也就是会变成正数。

确定边界

在每次判断时，根据不同的使用场景可以确定不同左右边界，可以直接使用mid值作为下一次的左/右边界，也可以使用mid+1/-1作为下一次的左/右边界。对于每种不同的方式，其结束循环的条件也有细微差异，需要仔细确认。

代码实现

public static int searchInsert(int[] nums, int target) {
        if (nums.length == 0) {
            return 0;
        }
        int left = 0, right = nums.length, mid;
        while (left <= right) {
            mid = (left + right) >>> 1;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }