二分查找
二分查找也叫二分搜索 (binary search),也叫折半查找 (half-interval search),是一种在有序数组中查找特定元素的搜索算法。
所以用二分查找的前提是数组必须是有序的,可以升序也可以降序
二分查找实现思路
以升序举例
即选择序列中间的数字和目标值进行比较
如果中间的数字小于目标值,说明包括中间数字在内的左半边区间的所有数字都小于目标值,可以全部排除。
如果中间的数字大于目标值,说明包括中间数字在内的右半边区间的所有数字都大于目标值,可以全部排除。
如果中间的数字等于目标值,则直接返回答案。
经典问题
设有100个已排好序的数据元素,采用折半查找时,最大比较次数为( A )
A.7
B.10
C.6
D.8
分析
假设找的是1:
第一次,和(1+100)/2=50比较,1~50;
第二次,和(1+50)/2=25比较,1~25;
第三次,和(1+25)/2=13比较,1~13;
第四次,和(1+13)/2=7比较,1~7;
第五次,和(1+7)/2=4比较,1~4;
第六次,和(1+4)/2=2比较,1~2;
第七次,和(1+2)/2=1比较找到结果1
比较次数也可以使用公式直接计算
⌈log100⌉=7 对log100向上取整
时间复杂度
最优时间复杂度
O(1)
平均时间复杂度
O(logn)
最坏时间复杂度
O(logn)
查找区间边界
例题
给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1
输入
输出
解释: 3 出现在 nums 中并且下标为 3
左闭右闭
大致思路
1 left从0开始 right到numSize-1结束
2 mid=left+(right-left)/2 或left+(right-left)/2+1都可以
3 left
4 left=mid+1 right=mid-1
示例程序
左闭右开
大致思路
1 left从0开始 right到numSize结束
2 mid=left+(right-left)/2
3 left
4 left=mid+1 right=mid
示例程序
左开右闭
大致思路
1 left从-1开始 right到numSize-1结束
2 mid=left+(right-left)/2+1 不断向左收缩
3 left
4 left=mid right=mid-1
参考程序
左开右开
1 left从-1开始 right到numSize结束
2 mid=left+(right-left)/2
3 left+1
4 left=mid right=mid
领取专属 10元无门槛券
私享最新 技术干货