二分查找

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

输入

nums = [0,1,2,3,4,5,6], target = 3

输出

3

解释: 3 出现在 nums 中并且下标为 3

左闭右闭

打开网易新闻 查看更多图片

大致思路

1 left从0开始 right到numSize-1结束

2 mid=left+(right-left)/2 或left+(right-left)/2+1都可以

3 left<=right 只剩下一个元素时需要判断是否符合

4 left=mid+1 right=mid-1

示例程序

#include
using namespace std;
//nums查找数组 numsSize 数组元素个数 target 要查找的数
int binarySearch(int nums[],int numsSize,int target){
int left=0;// 数组开始元素0
int right=numsSize-1;//数组最后一个元素下标
int ans=-1;//查找不到返回-1
while(left<=right){//
int mid=left+(right-left)/2;// 也可以 mid=(left+right)/2 需要注意left+right超范围
if(target//左半部分查找
right =mid-1;
}else if(target>nums[mid]){//又半部分查找
left = mid + 1;
}else{//查到
ans=mid;
break;

return ans;

int main(){
int a[]={0,1,2,3,4,5,6};
int nSize=sizeof(a)/sizeof(a[0]);
int ret = binarySearch(a,nSize,3);
cout<}
/*
输出
3
*/

左闭右开

打开网易新闻 查看更多图片

大致思路

1 left从0开始 right到numSize结束

2 mid=left+(right-left)/2

3 left

4 left=mid+1 right=mid

示例程序

#include
using namespace std;
//nums查找数组 numsSize 数组元素个数 target 要查找的数
int binarySearch(int nums[],int numsSize,int target){
int left=0;//开始元素0
int right=numsSize;//数组最后一个元素下标+1
int ans=-1;//查找不到返回-1
while(left//此处没有=
int mid=left+(right-left)/2;// 也可以 mid=(left+right)/2 需要注意left+right超范围
if(target right =mid;//在左半部分找 比mid小，由于右边开区间 需要包括mid
}else if(target>nums[mid]){
left = mid + 1;//闭区间 比mid大 需要mid+1
}else{//查到 中断结束
ans=mid;
break;

return ans;

int main(){
int a[]={0,1,2,3,4,5,6};
int nSize=sizeof(a)/sizeof(a[0]);
int ret = binarySearch(a,nSize,3);
cout<}
/*
输出
3
如果int ret = binarySearch(a,nSize,-1);
无结果输出
*/

左开右闭

打开网易新闻 查看更多图片

大致思路

1 left从-1开始 right到numSize-1结束

2 mid=left+(right-left)/2+1 不断向左收缩

3 left

4 left=mid right=mid-1

参考程序

#include
using namespace std;
//nums查找数组 numsSize 数组元素个数 target 要查找的数
int binarySearch(int nums[],int numsSize,int target){
int left=-1;//-1开始
int right=numsSize-1;//数组最后一个元素下标
int ans=-1;//查找不到返回-1
while(left int mid=left+(right-left)/2+1;
if(target right=mid+1;//右闭合
}else if(target>nums[mid]){
left=mid;//左开
}else{//查到退出
ans=mid;
break;

return ans;

int main(){
int a[]={0,1,2,3,4,5,6};
int nSize=sizeof(a)/sizeof(a[0]);
int ret = binarySearch(a,nSize,3);
cout<}
/*
输出
3
*/

左开右开

打开网易新闻 查看更多图片

1 left从-1开始 right到numSize结束

2 mid=left+(right-left)/2

3 left+1

4 left=mid right=mid

#include
using namespace std;
//nums查找数组 numsSize 数组元素个数 target 要查找的数
int binarySearch(int nums[],int numsSize,int target){
int left=-1;//-1开始
int right=numsSize;//数组最后一个元素下标
int ans=-1;//查找不到返回-1
while(left+1 int mid=left+(right-left)/2;
if(target right=mid;//右闭合
}else if(target>nums[mid]){
left=mid;//左开
}else{//查到退出
ans=mid;
break;

return ans;

int main(){
int a[]={0,1,2,3,4,5,6};
int nSize=sizeof(a)/sizeof(a[0]);
int ret = binarySearch(a,nSize,3);
cout<}
/*
输出
3
*/

CSP初赛复习-25-二分查找-练习题

完善程序：
（切割绳子）有 n 条绳子，每条绳子的长度已知且均为正整数。绳子可以以任意正整数长度切割，但不可以连接。现在要从这些绳子中切割出 m条长度相同的绳段，求绳段的最大长度是多少。（第一、二空 2.5 分，其余 3 分）

输入：第一行是一个不超过 100 的正整数 n，第二行是 n个不超过 10^6 的正整数，表示每条绳子的长度，第三行是一个不超过 10^8的正整数 m。

输出：绳段的最大长度，若无法切割，输出Failed。

#include
using namespace std;
int n, m, i, lbound, ubound, mid, count;
int len[100]; // 绳子长度
int main()
cin >> n;
count = 0;
for (i = 0; i < n; i++)
cin >> len[i];
①;
cin >> m;
if (②)
cout << "Failed" << endl;
return 0;
lbound = 1;
ubound = 1000000;
while (③)
mid = ④;
count = 0;
for (i = 0; i < n; i++)
⑤;
if (count < m)
ubound = mid - 1;
else
lbound = mid;
cout << lbound << endl;
return 0;