c++ - 使用向量进行二分搜索需要很长时间
问题描述
我使用向量在 C++ 中实现了二进制搜索算法,因为数组的长度不是固定的。但是,向量实现比我使用数组的其他实现花费了更长的时间。有人可以帮我理解为什么会这样吗?
#include <iostream>
#include<stdlib.h>
#include<time.h>
#include<bits/stdc++.h>
using namespace std;
int BinSearch(long long int arr[],int key,int l,int r)
{
if(r<l){return -1;}
int mid = (l+r)/2;
if(arr[mid]==key){return mid;}
else if(arr[mid] < key)
{
return BinSearch(arr,key,mid+1,r);
}
else{return BinSearch(arr,key,l,mid-1);}
}
int main()
{
int n,k;
cin >> n;
long long int N[n];
long long int inp;
for(int i=0;i<n;i++)
{
cin >> inp;
N[i] = inp;
}
cin >> k;
long long int keys[k],ans[k];
for(int i=0;i<k;i++)
{
cin >> inp;
keys[i] = inp;
}
for(int i=0;i<k;i++)
{
ans[i] = BinSearch(N,keys[i],0,n-1);
}
for(int i=0;i<k;i++)
{
cout << ans[i] << " ";
}
return 0;
}
向量实现和数组实现之间的唯一区别是我使用向量来存储要执行二进制搜索的给定数字并存储键。我使用了 pushback() 操作。
解决方案
推荐阅读
- css - 如何在本机反应中使用百分比制作圆形视图?
- php - 找不到对象 xamp
- .net - windows库项目可以实现依赖注入吗?
- spring-boot - Spring boot 1.5.x jetty server gzip 不工作请求方法不是 GET
- java - 在 Android Q 中无法从“android.location.ILocationManager”中找到方法 reportLocation()
- python - 无法在 Python 中打开 URL 而不先在浏览器中打开它
- c++ - Qt C++ QPixmap 仅适用于绝对路径,如何在不使用 Qt 资源的情况下解决?
- r - R中基于Log-Cosh损失函数的线性回归模型
- html - 无法在模态中滚动 div
- reactjs - 如何在我的反应应用程序中使用我的自定义字体家族