给出一个队列和要查找的数值，找出数值在队列中的位置，队列位置从1开始
要求使用带哨兵的顺序查找算法
第一行输入n，表示队列有n个数据
第二行输入n个数据，都是正整数，用空格隔开
第三行输入t，表示有t个要查找的数值
第四行起，输入t个数值，输入t行
每行输出一个要查找的数值在队列的位置，如果查找不成功，输出字符串error
样例查看模式?
正常显示查看格式
8\n
33?66?22?88?11?27?44?55\n
3\n
22\n
11\n
99\n
3\n
5\n
error\n
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
vector<int>v(n+1);
for(int i=1;i<=n;i++)
{
cin>>v[i];
}
int m;
cin>>m;
while(m--)
{
int x;
cin>>x;
int k=n;
while(k)
{
if(v[k]==x)
{
break;
}
k--;
}
if(k)
{
cout<<k<<endl;
}
else
{
cout<<"error"<<endl;
}
}
return 0;
}给出一个队列和要查找的数值，找出数值在队列中的位置，队列位置从1开始
要求使用折半查找算法
第一行输入n，表示队列有n个数据
第二行输入n个数据，都是正整数，用空格隔开
第三行输入t，表示有t个要查找的数值
第四行起，输入t个数值，输入t行
每行输出一个要查找的数值在队列的位置，如果查找不成功，输出字符串error
样例查看模式?
正常显示查看格式
8\n
11?22?33?44?55?66?77?88\n
3\n
22\n
88\n
99\n
2\n
8\n
error\n
#include<iostream>
using namespace std;
const int N = 1e5;
int a[N];
int n;
bool flag = 0;
void find(int l, int r,int k)
{
if (l > r)return;
int mid = (l + r) / 2;
if (a[mid] == k)
{
flag = 1;
cout << mid << endl;
return;
}
else if (a[mid] < k)
{
find(mid + 1, r, k);
}
else
{
find(l, mid - 1, k);
}
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
int k;
cin >> k;
while (k--)
{
flag = 0;
int x;
cin >> x;
find(1,n,x);
if (!flag)cout << "error" << endl;
}
return 0;
}给出一个队列和要查找的数值，找出数值在队列中的位置，队列位置从1开始
要求使用顺序索引查找算法，其中索引表查找和块内查找都采用不带哨兵、从头开始的顺序查找方法。
第一行输入n，表示主表有n个数据
第二行输入n个数据，都是正整数，用空格隔开
第三行输入k，表示主表划分为k个块，k也是索引表的长度
第四行输入k个数据，表示索引表中每个块的最大值
第五行输入t，表示有t个要查找的数值
第六行起，输入t个数值，输入t行
每行输出一个要查找的数值在队列的位置和查找次数，数据之间用短划线隔开，如果查找不成功，输出字符串error
样例查看模式?
正常显示查看格式
18\n
22?12?13?8?9?20?33?42?44?38?24?48?60?58?74?57?86?53\n
3\n
22?48?86\n
6\n
13\n
5\n
48\n
40\n
53\n
90\n
3-4\n
error\n
12-8\n
error\n
18-9\n
error\n
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int>v(n);
for (int i = 0; i < n; i++)
{
cin >> v[i];
}
int k;
cin >> k;
vector<int>index(k);
for (int i = 0; i < k; i++)
{
cin >> index[i];//每一块中的最大值
}
int t;
cin >> t;
while (t--)
{
int x;
cin >> x;
int idx = -1;
int cnt = 0;
for (int i = 0; i < k; i++)
{
cnt++;//查找次数加加
if (x <= index[i])//一定在index[i]这个块里！
{
idx = i;
break;
}
}
if (idx == -1)
{
cout << "error" << endl;
continue;
}
bool ok = 0;
//两块之间的间隔是n/k!!
//范围是一块的头到另一块的头！
for (int i = idx * (n/k); i < (idx+1)*(n/k); i++)
{
cnt++;
if (x == v[i])
{
ok = 1;
cout << i + 1 << "-" << cnt << endl;
break;
}
}
if (!ok)
{
cout << "error" << endl;
}
}
return 0;
}假定输入y是整数，我们用折半查找来找这个平方根。在从0到y之间必定有一个取值是y的平方根，如果我们查找的数x比y的平方根小，则x2<y，如果我们查找的数x比y的平方根大，则x2>y，我们可以据此缩小查找范围，当我们查找的数足够准确时（比如满足|x2-y|<0.00001），就可以认为找到了y的平方根。
比如求5的平方根x，则x一定满足0<=x<=5，取x为(5+0)/2=2.5，因为2.5的平方为6.25>5，所以x一定小于2.5，也即x满足0<=x<=2.5，取x为1.25，以此类推
| X的范围 | X的取值 | x2 | x2-y | |
|---|---|---|---|---|
| 0 | 5 | 2.5 | 6.25 | 1.25 |
| 0 | 2.5 | 1.25 | 1.5625 | -3.4375 |
| 1.25 | 2.5 | 1.875 | 3.515625 | -1.484375 |
| 1.875 | 2.5 | 2.1875 | 4.78515625 | -0.21484375 |
| 2.1875 | 2.5 | 2.34375 | 5.4931640625 | 0.4931640625 |
| 2.1875 | 2.34375 | 2.265625 | 5.133056640625 | 0.133056640625 |
| 2.1875 | 2.265625 | 2.2265625 | … | … |
最后求得5的平方根为2.236
温馨提示：?计算过程中为确保精确性，计算变量的类型都用double
保留小数位数的输出，C语言参考格式printf("%.3lf\n",x) ；C++参考cout<<fixed<<setprecision(3)<<x<<endl;（要包含头文件Iomanip）
程序框架参考平时练习中折半查找的方法
第1行输入一个整数n(<100)，表示有n个数
从第2行起到第n+1行输入n个整数
输出n个数的平方根，精确到小数点后三位。
样例查看模式?
正常显示查看格式
2\n
13\n
5\n
3.606\n
2.236
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
while(n--)
{
double x;
cin>>x;
double l=1,r=x;
bool ok=0;
while(r-l>=0.00000001)
{
double mid=(l+r)/2;
if(abs(mid*mid-x)<=0.0000001)
{
printf("%.3lf\n",mid);
break;
}
else if(mid*mid-x>0.00000001)
{
r=mid;
}
else
{
l=mid;
}
}
}
return 0;
}已知有两个等长的非降序序列S1, S2, 设计函数求S1与S2并集的中位数。有序序列A?0??,A?1??,?,A?N?1??的中位数指A?(N?1)/2??的值,即第?(N+1)/2?个数（A?0??为第1个数）。
只需考虑中位数唯一的情况
输入分三行。第一行给出序列的公共长度N（0<N≤100000），随后每行输入一个序列的信息，即N个非降序排列的整数。数字用空格间隔。
在一行中输出两个输入序列的并集序列的中位数。
样例查看模式?
正常显示查看格式
5\n
1?3?5?7?9\n
2?3?4?5?6
4
#include<bits/stdc++.h>
using namespace std;
// 1 3 5 7 9
// 2 3 4 5 6
// 1 2 3 3 4 5 5 6 7 9
int main()
{
int n;
cin>>n;
vector<int>v(2*n);
for(int i=0;i<2*n;i++)
{
cin>>v[i];
}
sort(v.begin(),v.end());
cout<<v[n-1]<<endl;
return 0;
}单链表结点的存储结构包含两部分：数据、下一结点指针（默认为空）。
单链表包含头结点，存储实际数据的结点位置从1开始。
现输入一批无序的整数队列，编写程序完成以下要求
1）构建单链表并且把数据按递增顺序插入到链表中，并且统计非空指针发生变化的次数。
例如在初始只包含头结点的单链表中，依次插入3和2
当把3插入时，是头结点的next指针发生变化，初始头结点的next指针是空的，现在指向3的结点，所以不计入指针变化次数。
当把2插入时，它是插入到头结点和3结点之间，这时候头结点的next指针从指向3变成指向2，因此这次计入指针变化次数。
总之，如果是把一个空的next指针指向新的结点，则不计入变化次数；如果是把一个非空next指针修改指向新结点则计入变化次数。
2）实现对单链表的元素查找。输入一个链表位置，返回该位置对应的数据。如果位置非法则输出提示信息，看样例。
要求：必须使用单链表结构实现上述要求，并且不能用第三方算法库或容器类对象
第一行：第一个数字n表示样本数目，其后跟n个样本。
第二行：查找测试次数m 后跟m个待查找的位置。
第一行输出构建链表过程中，非空指针变化的总次数，格式看样本
第二行输出单链表创建后，从头到尾依次输出链表中元素数据
第三行到第n+1行，对每个查找位置，若结点存在，输出结点数据；否则输出error
样例查看模式?
正常显示查看格式
6?1?8?5?2?4?3\n
4?0?2?10?6\n
非空指针变化4次\n
1?2?3?4?5?8\n
error\n
2\n
error\n
8\n
#include<iostream>
using namespace std;
struct node
{
int data;
node* next;
node()
{
next = NULL;
}
};
class linkk
{
node* head;
int n;
int cnt;
public:
linkk()
{
n = 0;
cnt = 0;
head = new node;
}
void insert(int x)
{
node* temp = new node;
temp->data = x;
temp->next = NULL;
node* s = new node;
s = head;
while (1)
{
if (s->next == NULL)//直接插在后面
{
s->next = temp;
break;
}
if (s->next->data > x)
{
cnt++;//指针变化次数
temp->next = s->next;
s->next = temp;
break;
}
s = s->next;//注意！
}
n++;
}
void display()
{
cout << "非空指针变化" << cnt << "次" << endl;
node* k = new node;
k = head;
for (int i = 0; i < n - 1; i++)
{
k = k->next;
cout << k->data << " ";
}
k = k->next;
cout << k->data << endl;
}
int find(int x)
{
node* s = new node;
s = head;
if (x > n || x <= 0)
{
return -1;
}
for (int i = 0; i < x; i++)
{
s = s->next;
}
return s->data;
}
};
int main()
{
int nn;
cin >> nn;
linkk ll;
for (int i = 0; i < nn; i++)
{
int x;
cin >> x;
ll.insert(x);
}
ll.display();
int m;
cin >> m;
while (m--)
{
int x;
cin >> x;
if (ll.find(x) != -1)
{
cout << ll.find(x) << endl;
}
else
{
cout << "error" << endl;
}
}
return 0;
}