2023CSP初赛备考复习||二分查找

二分查找

二分查找也叫二分搜索 (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