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超出了子表的個數，找不到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;
}
)
