顺序索引查找

时间限制: 1 Sec  内存限制: 128 MB

题目描述

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

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

输入

第一行输入n,表示主表有n个数据
第二行输入n个数据,都是正整数,用空格隔开
第三行输入k,表示主表划分为k个块,k也是索引表的长度
第四行输入k个数据,表示索引表中每个块的最大值
第五行输入t,表示有t个要查找的数值
第六行起,输入t个数值,输入t行

输出

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

样例输入

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

样例输出

3-4
error
12-8
error
18-9
error

解决方案

#include <iostream>
#include <algorithm>
void find(int *maximum, int *point, int *p, int size) {
    for (int i = *point; i <= size; ++i) {
        if (maximum[0] < p[i]) {
            maximum[1] = --i;
            *point = i;
            return;
        }
    }
    maximum[1] = size;
}
int half_search(const int a[], int key, int low, int high) {
    if (low > high) {
        return 0;
    }
    int mid = (low + high) / 2;
    if (a[mid] == key) {
        return mid;
    } else if (a[mid] > key) {
        half_search(a, key, low, mid - 1);
    } else {
        half_search(a, key, mid + 1, high);
    }
    return 0;
}
int find_block(int **maximum, int max_size, int flag, int *find) {
    for (int i = 0; i < max_size; ++i) {
        (*find)++;
        if (flag <= maximum[i][0]) {
            return i;
        }
    }
    return max_size - 1;
}
int find_flag(int block, int **maximum, int max_size, int flag, int *find, const int *p) {
    int low, high;
    if (block == 0) {
        low = 1;
        high = maximum[block][1];
    } else {
        low = maximum[block - 1][1] + 1;
        high = maximum[block][1];
    }
    for (int i = low; i <= high; ++i) {
        (*find)++;
        if (flag == p[i]) {
            return i;
        }
    }
    return 0;
}
int main() {
    size_t size;
    std::cin >> size;
    //input array
    int *p = new int[size + 1];
    for (size_t i = 1; i <= size; ++i) {
        std::cin >> p[i];
    }
    //input maximum
    int max_size, point = 1, index;
    std::cin >> max_size;
    int **maximum = new int *[max_size];
    for (int k = 0; k < max_size; ++k) {
        maximum[k] = new int[2];
    }
    for (int j = 0; j < 3; ++j) {
        std::cin >> index;
        maximum[j][0] = index;
        find(maximum[j], &point, p, size);
    }
    //input index
    int index_size;
    std::cin >> index_size;
    for (int l = 0; l < index_size; ++l) {
        int find = 0, flag = 0;
        std::cin >> flag;
        int value;
        value = find_flag(find_block(maximum, max_size, flag, &find), maximum, max_size, flag, &find, p);
        if (value) {
            std::cout << value << "-" << find << std::endl;
        } else {
            std::cout << "error" << std::endl;
        }
    }
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇