c++实现:.随机产生n(n>500)个整数,完成以下操作: (1)对给定的查找集合,顺序查找与给定值k相等的元素,并返回查找所用时间; (2)对给定的有序查找集合,折半查找与给定值k相等的元素,并返回查找所用时间;时间用纳秒输出
时间: 2024-01-22 14:19:33 浏览: 43
以下是C++代码实现,使用了chrono库计算时间,包含了随机生成n个整数,顺序查找和折半查找两种算法:
```
#include <iostream>
#include <chrono>
#include <algorithm>
using namespace std;
int main() {
int n = 1000; // 生成n个整数
int k = 123; // 给定值k
int arr[n];
for (int i = 0; i < n; i++) {
arr[i] = rand();
}
sort(arr, arr + n); // 对数组进行排序
// 顺序查找
auto start = chrono::high_resolution_clock::now();
for (int i = 0; i < n; i++) {
if (arr[i] == k) {
break;
}
}
auto end = chrono::high_resolution_clock::now();
auto time = chrono::duration_cast<chrono::nanoseconds>(end - start).count();
cout << "顺序查找用时:" << time << "纳秒" << endl;
// 折半查找
start = chrono::high_resolution_clock::now();
int l = 0, r = n - 1;
while (l <= r) {
int mid = (l + r) / 2;
if (arr[mid] == k) {
break;
} else if (arr[mid] > k) {
r = mid - 1;
} else {
l = mid + 1;
}
}
end = chrono::high_resolution_clock::now();
time = chrono::duration_cast<chrono::nanoseconds>(end - start).count();
cout << "折半查找用时:" << time << "纳秒" << endl;
return 0;
}
```