C++关于数组中元素的快捷查找

C++关于数组中元素的快捷查找。

在一个数组里查找某个元素的位置方法有线性查找和折半查找两种。
先说线性查找，即为遍历数组的所有元素，若找到相对应的值则打印其索引值。

#include<cstdio>
int main(){
int a[1000000],n，k,m;
scanf("%d%d",&n，&k);//n表示输入数个数，k表示需要查找元素的个数
for(int i=0;i<n;i++){scanf("%d",a+i);}
for(int j=0;j<k;k++){
scanf("%d",&m);
if(m==a[j])printf("%d ",j+1);
}
}

可以看到这种方法为初学者常使用的，但处理大量数据起来十分耗时。
这里我们介绍一种能降低时间复杂度的优化算法，叫折半查找，可大大提高计算机运行效率。
折半查找常用于元素从小到大的数组，通过不断取平均值，并通过比较其与目标值的大小，来调整位置。
大致思路如下：
在有n个元素并元素大小依次递增的数组a[]中，

• left=0,right=n-1;
• middle=(left+right)/2;
• 如果key>a[middle],那么left=middle+1;如果key<a[middle],那么right=middle-1；
• 直到key=a[middle]为止

话不多说，代码跑起

1. 迭代版本

#include <stdio.h>
int n,k,numbers[1000001],m,l,r,mid,b;
int main() {
// 反复读入数字和查找数字的数量
while (scanf("%d%d", &n, &k) != EOF) {
// 读入给定的数字
for (int i = 0; i < n; i++) {
scanf("%d", &numbers[i]);
}
for (int j = 0; j < k; j++) {
l=0;r=n-1;
scanf("%d", &m);
while(l<=r){
mid = (l + r) / 2;b=1;
if (numbers[mid]==m)
{printf("%d",mid+1);b=0;break;}
else if (numbers[mid] < m)
{l=mid+1;}
else
{ r = mid - 1;}
}
if(b){printf("%d",0);}
if(j<k-1)printf(" ");
}
}
return 0;
}

2.递归版本

#include<stdio.h>
int find(int,int,int);
int n,k,a[1000000]={},m,mid;
int main(){
while(scanf("%d%d",&n,&k)!=EOF) {
for (int i = 0; i < n; i++) { scanf("%d", (a + i)); }
for (int j = 0; j < k; j++) {
scanf("%d", &m);
j == 0 ? printf("%d", find(0, n - 1, m)) : printf(" %d", find(0, n - 1, m));
}
}
return 0;
}
int find(int l,int r,int b ){
mid=(l+r)/2;
if(b==a[mid]){return mid+1;}
if(l>r){return 0;}
if( b>a[mid])return find(mid+1,r,b);
else return find(l,mid-1,b);
}

这样就大大得减少了查找的时间了哦。
如果输入的数据过多我们也可以把scanf或cin换为快读，快读模板如下

inline int read()
{
int X=0; bool f=1;
char ch=getchar();
while(ch<'0'||ch>'9') {
if(ch=='-'){ f=0; }
ch=getchar();
}
while(ch>='0'&&ch<='9') {
X=X*10+ch-'0';
ch=getchar();}
return X*f;
}

然后以这种方式读入数组

for(int i=0;i<n;i++){a[i]=read();}

或者指针传递的方式

inline int read(int*X)
{
bool f=1;
char ch=getchar();
while(ch<'0'||ch>'9') {
if(ch=='-'){ f=0; }
ch=getchar();
}
while(ch>='0'&&ch<='9') {
*X=*X*10+ch-'0';
ch=getchar();}
return X*f;
}

以此方式读入

for(int i=0;i<n;i++){read(a+i);}

用以上方法可以加快程序运行的效率！
觉得文章对你有所帮助，可以点个赞哦！

最后

以上就是玩命手机为你收集整理的C++关于数组中元素的快捷查找的全部内容，希望文章能够帮你解决C++关于数组中元素的快捷查找所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。