Description
给出一个队列和要查找的数值，找出数值在队列中的位置，队列位置从1开始
要求使用顺序索引查找算法，其中索引表查找和块内查找都采用不带哨兵、从头开始的顺序查找方法。
Input
第一行输入n，表示主表有n个数据
第二行输入n个数据，都是正整数，用空格隔开
第三行输入k，表示主表划分为k个块，k也是索引表的长度
第四行输入k个数据，表示索引表中每个块的最大值
第五行输入t，表示有t个要查找的数值
第六行起，输入t个数值，输入t行
Output
每行输出一个要查找的数值在队列的位置和查找次数，数据之间用短划线隔开，如果查找不成功，输出字符串error
Sample
#0
Input
18
22 12 13 8 9 20 33 42 44 38 24 48 60 58 74 57 86 53
3
22 48 86
6
13
5
48
40
53
90
Output
3-4
error
12-8
error
18-9
error
解题思路
一开始忘记了n可能无法整除k，导致在构建每个块的时候出错一直卡了很久
AC代码
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 10010;
int arr[N];
int n, k;
struct indexBlock
{
int start;
int end;
int max;
}indexBlocks[N];
int blockSearch(int key, int& cnt)
{
int i = 1, j;
while (i <= k &&++cnt&& key > indexBlocks[i].max) {
i++; }//确认key所在的是哪个子表
if (i > k)return 0;//i超出了子表的个数，找不到key
j = indexBlocks[i].start;//j为key所在子表起始下标
while (j <= indexBlocks[i].end &&++cnt&& arr[j] != key) {
j++; }//在确定的块内寻找key
if (j > indexBlocks[i].end)return 0;//j超出了所在块范围，没有找到key
return j;
}
int main()
{
while (cin >> n)
{
for (int i = 1; i <= n; i++)
{
cin >> arr[i];
}
int j = 0;
cin >> k;
for (int i = 1; i <= k; i++)
{
int max;
cin >> max;
indexBlocks[i].start = j + 1;//块的起始下标
j = j + 1;
// 找到第一个大于max的数，此时j-1就是块的结束下标
while (j < n)
{
j++;
if (arr[j] > max)
{
j--;
break;
}
}
indexBlocks[i].end = j;
indexBlocks[i].max = max;
}
int t;
cin >> t;
while (t--)
{
int key, cnt = 0;
cin >> key;
int index = blockSearch(key, cnt);
if (index)cout << index << "-" << cnt << endl;
else cout << "error" << endl;
}
}
return 0;
}
