二分初解

适用范围

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

思想

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

划分的具体过程

如下列数组{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,也就是会变成正数。

确定边界

在实际实现时,确定左右边界是需要考虑好几种情况的,如上表是将数组的下标直接用作左右边界。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public 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;
}
}
return left;
}