М-блочный поиск
Этот способ удобен при индексном хранении списка. Предполагается, что исходный
упорядоченный список B длины N разбит на M подсписков B1,B2,...,Bm длины N1,N2,...,Nm,
таким образом, что B=B1,B2,..,Bm.
Для нахождения ключа V, нужно сначала определить первый из списков Bi, i=1,M, последний
элемент которого больше V, а потом применить последовательный поиск к списку Bi.
Хранение списков Bi может быть связным или последовательным. Если длины всех подсписков
приблизительно равны и M= N, то Max М-блочного поиска равен 2 N. При одинаковой частоте
использования элементов Avg М-блочного поиска равен N.
Описанный алгоритм усложняется, если не известно, действительно ли в списке имеется
элемент, совпадающий с ключом V. При этом возможны случаи: либо такого элемента в списке
нет, либо их несколько.
Если вместо ключа V имеется упорядоченный список ключей, то последовательный или
М-блочный поиск может оказаться более удобным, чем бинарный, поскольку не требуется
повторной инициализации для каждого нового ключа из списка V.