二分法-二分查找中极易出错的点及其解决伪代码

1.使用条件

针对一组单调（增、减）的数列

2.举例（附带步骤）

12 15 23 27 34 39 41 49 52 56

查找目标key:39 在哪个位置，就可以用二分查找

步骤一：把数列放到数组中，两个指针分别指向头和尾，mid=（left+right）/2

步骤二：判断key>a[mid],更新left=mid+1；然后更新mid，方法同步骤一

步骤三：判断key<a[mid],更新right=mid-1；然后更新mid，方法同步骤一

步骤四：key=a[mid]；找到key了

3.代码易错点

（1）写while循环时，left < right 还是 left <= right

（2）if (number [middle] > target),更新右区间，那么right = middle 还是right = middle-1

4.循环不变量

?区间的定义可以理解为循环的不变量，在边界处理的时候要坚持区间开闭的原则

一般两种情况：[left,right]? 左闭右闭??[left,right) 左闭右开

5.左闭右闭 [left,right]?写法（伪代码）

left=0;

right?= num.size-1;

while ( left <= right ){

? ? middle = (left+right)/2;

? ? if( num [middle] > targrt )

? ? ? ? ? ? right = middle -1;

? ? else if (num[middle]? < target )

? ? ? ? ? ? left = middle+1;

? ? else return middle;

}

return? -1;

6.左闭右开?[left,right) 写法（伪代码）

left = 0;

right?= num.size;

while ( left <?right ){

? ? middle = (left+right)/2;

? ? if( num [middle] > targrt )

? ? ? ? ? ? right = middle;

? ? else if (num[middle]? < target )

? ? ? ? ? ? left = middle+1;

? ? else return middle;

}

return? -1;