Индексно-последовательный поиск

Алгоритмы сортировки и поиска / Индексно-последовательный поиск

 

Для индексно-последовательного поиска в дополнение к отсортированной таблице заводится вспомогательная таблица, называемая индексной.

Каждый элемент индексной таблицы состоит из ключа и указателя на запись в основной таблице, соответствующей этому ключу. Элементы в индексной таблице, как элементы в основной таблице, должны быть отсортированы по этому ключу.

Если индекс имеет размер, составляющий 1/8 от размера основной таблицы, то каждая восьмая запись основной таблицы будет представлена в индексной таблице.
Индексная таблица
Если размер основной таблицы — n, то размер индексной таблицы — ind_size = n/8.

Достоинство алгоритма индексно-последовательного поиска заключается в том, что сокращается время поиска, так как последовательный поиск первоначально ведется в индексной таблице, имеющей меньший размер, чем основная таблица. Когда найден правильный индекс, второй последовательный поиск выполняется по небольшой части записей основной таблицы.

 
Реализация индексно-последовательного поиска на языке Си

1
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
#define _CRT_SECURE_NO_WARNINGS // для корректной работы scanf()
#include <stdio.h>
#include <stdlib.h> // для использования функций system()
int main()
{
  int k[20]; // массив ключей основной таблицы
  int r[20]; // массив записей основной таблицы
  int i, j, ind_size;
  int key;
  int kindex[3]; // массив ключей индексной таблицы
  int pindex[3]; // массив индексов индексной таблицы
  system("chcp 1251"); // перевод русского языка в консоли
  system("cls");     // очистка окна консоли
  // Инициализация ключевых полей упорядоченными значениями
  k[0] = 8;  k[1] = 14;
  k[2] = 26;  k[3] = 28;
  k[4] = 38;  k[5] = 47;
  k[6] = 56;  k[7] = 60;
  k[8] = 64;  k[9] = 69;
  k[10] = 70; k[11] = 78;
  k[12] = 80; k[13] = 82;
  k[14] = 84; k[15] = 87;
  k[16] = 90; k[17] = 92;
  k[18] = 98; k[19] = 108;
  // Ввод записей
  for (i = 0; i < 20; i++) 
  {
    printf("%2d. k[%2d]=%3d: r[%2d]= ", i, i, k[i], i);
    scanf("%d", &r[i]);
  }
  // Формирование индексной таблицы
  for (i = 0, j = 0; i < 20; i = i + 8, j++) 
  {
    kindex[j] = k[i]; // переносим каждый 8-й ключ в индексную таблицу
    pindex[j] = i;    // запоминаем текущий индекс
  }
  ind_size = j;  // запоминаем размер индексной таблицы
  pindex[j] = 20; // последний индекс равен 20
  // Поиск
  printf("Введите key: "); // вводим ключевое поле
  scanf("%d", &key);
  // Просматриваем элементы индексной таблицы
  for (j = 0; j < ind_size; j++) 
  {
    if (key < kindex[j]) // если находим ключ меньше введенного,
      break;           // выходим из цикла - мы нашли нужную область основной таблицы
  }
  if (j == 0)  i = 0;      // присваиваем i начальный индекс диапазона поиска в основной таблице
  else  i = pindex[j - 1];
  for (i; i<pindex[j]; i++) // осуществляем поиск в основной таблице
  {                         //до следующего индекса индексной таблицы
    if (k[i] == key)  // если найдено введенное значение, выводим его
      printf("%2d. key=%3d. r[%2d]=%3d", i, k[i], i, r[i]);
  }
  getchar(); getchar();
  return 0;
}

Результат выполнения
Результат индексно-последовательного поиска


Назад: Алгоритмы сортировки и поиска

Комментариев к записи: 3

  • Эффективность индексно-последовательного поиска O(корень квадратный из n) Количество сравнений - корень квадратный из n + 1

  • Дмитрий
    Отличный коммент выше, при сложности N + n/N, получается что бинарный поиск сильно лучше При n=10000, для бинарного log2(n) = 13, а для N + n/N = 100 + 10000/100 = 200

  • Максимальная вычислительная сложность, или количество сравнений, равно N + n/N, где N - размер индексной таблицы, n - общее количество элементов.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *