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

本文主要是介绍C : DS静态查找之顺序索引查找，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

给出一个队列和要查找的数值，找出数值在队列中的位置，队列位置从1开始

要求使用顺序索引查找算法，其中索引表查找和块内查找都采用不带哨兵、从头开始的顺序查找方法。

Input

第一行输入n，表示主表有n个数据

第二行输入n个数据，都是正整数，用空格隔开

第三行输入k，表示主表划分为k个块，k也是索引表的长度

第四行输入k个数据，表示索引表中每个块的最大值

第五行输入t，表示有t个要查找的数值

第六行起，输入t个数值，输入t行

Output

每行输出一个要查找的数值在队列的位置和查找次数，数据之间用短划线隔开，如果查找不成功，输出字符串error

Sample

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超出了子表的个数，找不到keyj = indexBlocks[i].start;//j为key所在子表起始下标while (j <= indexBlocks[i].end &&++cnt&& arr[j] != key) { j++;  }//在确定的块内寻找keyif (j > indexBlocks[i].end)return 0;//j超出了所在块范围，没有找到keyreturn 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;
}