Индексно-последовательный поиск предполагает, что в дополнение к отсортированной таблице ключей заводится вспомогательная таблица, называемая индексной.
Каждый элемент индексной таблицы состоит из ключа и указателя на запись в основной таблице, соответствующей этому ключу. Элементы в индексной таблице, как и элементы в основной таблице, должны быть отсортированы по этому ключу.
Если индекс имеет размер, составляющий 1/5 от размера основной таблицы, то каждая пятая запись основной таблицы будет представлена в индексной таблице. Шаг формирования индексной таблицы может быть задан в каждой конкретной реализации.
Если размер основной таблицы — n, то размер индексной таблицы — ind_size = n/step, где step — шаг формирования индексной таблицы.
Достоинство алгоритма индексно-последовательного поиска заключается в том, что сокращается время поиска, так как последовательный поиск первоначально ведется в индексной таблице, имеющей меньший размер, чем основная таблица. Когда найден правильный индекс, второй последовательный поиск выполняется по небольшой части записей основной таблицы.
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#define _CRT_SECURE_NO_WARNINGS // для корректной работы scanf() в Visual Studio
#include <stdio.h>
#include <stdlib.h> // для использования функций system()
int main()
{
// массив ключей основной таблицы
int k[] = { 8, 14, 26, 38, 72, 115, 206, 221,
229, 307, 318, 389, 411, 413, 473, 504, 518};
const int size = sizeof(k) / sizeof(int); // размер массива ключей
const int step = 5; // шаг индексной таблицы
int r[size]; // массив записей основной таблицы
const int ind_size = size/step+1;
int key, j;
int kindex[ind_size]; // массив ключей индексной таблицы
int pindex[ind_size]; // массив индексов индексной таблицы
system("chcp 1251"); // перевод русского языка в консоли
system("cls"); // очистка окна консоли
// Ввод записей
for (int i = 0; i < size; i++)
{
printf("k[%2d]=%3d: r[%2d]= ", i, k[i], i);
scanf("%d", &r[i]);
}
// Формирование индексной таблицы
for (int i = 0, j = 0; i < size; i = i + step, j++)
{
kindex[j] = k[i]; // переносим каждый step-ключ в индексную таблицу
pindex[j] = i; // запоминаем текущий индекс
}
printf("Индексная таблица:\n");
for (int i = 0; i < ind_size; i++)
{
printf("p[%2d]=%3d: индекс %3d\n", i, kindex[i], pindex[i]);
}
// Поиск
printf("Введите k: "); // вводим ключевое поле
scanf("%d", &key);
// Просматриваем элементы индексной таблицы
int beg, end; // начало и конец диапазона поиска
for (j = 0; j < ind_size; j++)
{
if (key < kindex[j]) // если находим ключ меньше введенного,
{
break; // выходим из цикла - мы нашли нужную область основной таблицы
}
}
int flag = 0;
if (j > 0) // если находимся в середине индексной таблицы
beg = pindex[j - 1];
else // если находимся до начального элемента индексной таблицы
beg = 0;
if (j == ind_size) // если дошли до конца таблицы
end = size; // ищем до последнего элемента основной таблицы
else
end = pindex[j]; // иначе ищем до следующего индекса
for (int i = beg; i < end; i++) // осуществляем поиск в основной таблице
{
if (k[i] == key) // если найдено введенное значение, выводим его
{
printf("Найдена запись %2d: k=%3d, r=%3d\n", i, k[i], r[i]);
flag = 1;
}
}
if (flag == 0)
{
printf("Запись не найдена!\n");
}
system("pause");
return 0;
}Результат выполнения
Эффективность индексно-последовательного поиска O(корень квадратный из n)
Количество сравнений — корень квадратный из n + 1
Отличный коммент выше, при сложности N + n/N, получается что бинарный поиск сильно лучше
При n=10000, для бинарного log2(n) = 13, а для N + n/N = 100 + 10000/100 = 200
Максимальная вычислительная сложность, или количество сравнений, равно
N + n/N, где N — размер индексной таблицы,
n — общее количество элементов.