当前位置:   article > 正文

查找算法——二分查找

二分查找

二分查找

目录

  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

在这里插入图片描述

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

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/Cpp五条/article/detail/437678
推荐阅读
相关标签
  

闽ICP备14008679号