我明可以for硬来的，但我选择乱排...
原题链接：8019.查找x
2023-12-22 22:48:13
发布于：浙江
70阅读
0回复
0点赞
思路：c++11随机数库出坐标乱试，同时标记上，之后判断是否全被标记了，如果是就直接就代表没这个数输出-1结束代码，否则while试坐标，就行了，所以说这个代码是乱排
代码实现:
#include <iostream>
#include <ctime>
#include <random>
using namespace std;
int n;
int a[101], b[101];//a数组是数值，b数组是标记
bool pan() {
bool flag=0;
for (int i = 1; i <= n; i++) {
if(!b[i]) return 1;
}
return flag;
}//判断函数，判断是否都是找过的
int main() {
cin >> n;
default_random_engine e;
uniform_int_distribution<int> u(1, n);//范围
e.seed(time(0));
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
int s;
cin >> s;
while (1) {
int x = u(e);//随机数
if (!pan()) {//判断 是不是在数组内，若不是就输出-1,结束程序
cout << "-1" << endl;
return 0;
}
if (a[x] == s) {
printf("%d\n", x);//找到就输出
break;//出while结束代码
} else b[x] = 1;//不是就标记
}
return 0;
}
随机数自主学习CSDN
话说有没有大佬分析下程序平均时间复杂度？
附二分正常代码
绝对十万分常规：
#include<bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
int a[n + 1] = {0};
for (int i = 1; i <= n; i++)scanf("%d", &a[i]);
int s;
cin >> s;
int l = 1, r = n;
while (l < r) {
int mid = (l + r) >> 1;
if (a[mid] >= s) r = mid;
if (a[mid] < s) l = mid + 1;
}
if (a[l] == s) cout << l << endl;
else cout << "-1" << endl;
return 0;
}
这里空空如也
有帮助，赞一个