C : DS静态查找之顺序索引查找

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;
}