查找算法——二分查找

二分查找

目录

1. 二分查找的简介
2. 二分查找的原理
3. 二分查找的优点
4. 二分查找中的问题
5. 二分查找的例题

二分查找的简介

二分查找(Binary search)也称折半查找，是一种效率较高的查找方法。二分查找的要求是查找的序列是单调的。

二分查找的原理

1. 设置区间，将要查找的数位于哪个区间，找到区间边界，下边界为bottom，上边界为top，通过中间值进行查找mid=(bottom+top)/2;
2. 比较target与arr[mid]的大小关系
   1. 如果target<arr[mid],那么就让top=mid-1；在左半区进行查找
   2. 如果target>arr[mid],那么就让bottom=mid+1；在右半区进行查找。
   3. 如果target=arr[mid]，那么就会查找查找成功返回mid值

二分查找的优点

时间复杂度问题：

• 二分查找最快是O(1);刚好目标值位于最中间
• 最复杂的查找的时间也是O(log2n),这样也会大大的减少了查找时间。我们所熟知的快排同样也使用了二分的思想

二分查找中的问题

进行查找时存在除法涉及的非整数，对于二分查找，无非是向上取整与向下取整，对于middle取整方向的选择，却决于我们使用的区间类型。如果是左闭右开区间[l,r)，则向下取整，因为左边是闭区间，也就是说左边边界是可以取到的，为了能取到左边界，我们必须向下取整；如果是左开右闭区间(l,r]，则向上取整，因为右边是闭区间，右边界可取到，所以必须向上取整；而对于闭区间[l,r]，middle的取整方向是无所谓的，向上或向下取整都可以。

二分查找的例题

1. 洛谷题单p2249

输入n个不超过 10的9次 的单调不减的（就是后面的数字不小于前面的数字）非负整数 a*1,a2,…,a**n，然后进行 m次询问。对于每次询问，给出一个整数q，要求输出这个数字在序列中第一次出现的编号，如果没有找到的话输出 −1 。

1. 进行暴力查找的方法会导致时间超时

#include<stdio.h>
int main(){
 int n,m;
 scanf("%d %d",&n,&m);
 int a[n];
 int str[m];
 int i;
 for(i=1;i<=n;i++){
  scanf("%d",&a[i]);
 }
 for(i=1;i<=m;i++){
  scanf("%d",&str[i]);
 }
 int j;
 int str1[m];
 for(i=1;i<=m;i++){
  for(j=1;j<=n;j++){
   if(str[i]==a[j]){
   str1[i]=j;
   break; 
   }
  }
  if(j==n+1){
   str1[i]=-1;
  }
 }
 for(i=1;i<=m;i++){
  if(i<m)
  printf("%d ",str1[i]);
  else
  printf("%d",str1[i]);
 }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

在这里会出现时间超时现象

当采用二分查找时就不会出现超时问题

#include<stdio.h>
int k;
	int a[1000000];
int search(int l,int r){//定义的左右边界
	int i;
	while(l<r){
		int mid=(l+r)/2;//同时这里会涉及边界问题，将要查找的内容可能会相同
		if(a[mid]>=k){//进行中间值与target的大小比较
			r=mid;
		}
		else{
			l=mid+1;
		}
	}
	return l;
}
int main(){
	int n,m;
	scanf("%d %d",&n,&m);
	int i;
	for(i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}  
	for(i=1;i<=m;i++){
		scanf("%d",&k);//进行输入
		int c=search(1,n);//返回查找的数值下表
		if(a[c]==k){
			printf("%d ",c);//如果查找相同则会返回值
			
		}
		else {
			printf("-1 ");/否则就会输出-1
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

2. 洛谷题单p2240

题目描述

木材厂有 n 根原木，现在想把这些木头切割成 k段长度均为 l的小段木头（木头有可能有剩余）。

当然，我们希望得到的小段木头越长越好，请求出 l的最大值。

木头长度的单位是 cm，原木的长度都是正整数，我们要求切割得到的小段木头的长度也是正整数。

例如有两根原木长度分别为 11和 21，要求切割成等长的 6 段，很明显能切割出来的小段木头长度最长为 5。

当进行不是太正规的二分查找时，同样也会出现时间超时现象

#include<stdio.h>
int search();
int k;
int n;
int a[100000];
int main(){	
	scanf("%d %d",&n,&k);
	int i;
	for(i=0;i<n;i++){
		scanf("%d",&a[i]);
	}
	int c;
	c=search();
	printf("%d",c);
}
int search(){
	int i;
	int sum=0;
	for(i=0;i<n;i++){
		sum=sum+a[i];//计算木材总长度
	}
	int t=sum/k;//假设一根木材分成k段，这是所能分出的最大的长度
	int val=0;
	while(1){
	
	for(i=0;i<n;i++){
		val=val+a[i]/t;//再用每一根除以均值，计算可以分出几段，如果分出来的与所要求的相同，那么直接返回这个平均值
	}	
	if(val==k){//进行比较，这里存在val=k与val<k的情况
		break;
	}
	else {
		t=t-1;
	}
	val=0;}
	return t;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

因为上面存在一种情况使的时间相对运行的较长，当平均值远大于所有木段的最小值时，会导致时间偏长。

所以对以上代码进行了优化

#include<stdio.h>
int a[100005],n;
long long sum(int k){
	long long ans=0;//一定要开long long,使用int范围不满足所需求的大小
	for(int i=1;i<=n;i++){//计算以 k 为一段的长度可以分为几段
		ans=ans+1ll*a[i]/k;
	}
	return ans;//返回答案
}
	int find(int l,int r,int k){
	if(l>r)return 0;
	int mid=(l+r)/2,i;
	long long ans=sum(mid);//计算段数
	if(ans==k)return mid;
	if(ans>k){
		if(sum(mid+1)<k)return mid;
		else return find(mid+1,r,k);
	}
	else return find(l,mid-1,k);
}
int main(){
	int i,max=0,k;
	scanf("%d%d",&n,&k);//输入
	for(i=1;i<=n;i++){
		scanf("%d",&a[i]);
		if(a[i]>max)
            max=a[i];
	}
	int h=find(1,max,k),flag=0;//h为二分返回的答案
	if(!h){//判断输出，此条件代表分不出大于等于 1cm 小段的情况
		printf("0");return 0;
	}
	while(sum(h)==k){
		h++;flag=1;
	}
	printf("%d",h-flag);//输出
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

以上就是二分查找的全部内容，是不是觉得大飞的博客写的很好，手动点个赞吧！！！