Глава 3. Сортировка и поиск

Введение в поиск

Алгоритмы поиска занимают важное место в прикладных алгоритмах. Обычно данные хранятся в определенном образом упорядоченном наборе. Найти некоторую запись из этого набора — вот классическая задача программирования, вокруг которой сгенерировано множество идей [1, 3, 9, 10, 13].

Пусть мы имеем таблицу, состоящую из записей (табл. 3.1). Первое поле каждой записи содержит ключ (например, табельный номер); второе — фамилию и так далее. Ключом может любое поле записи.

Таблица 3.1

	Иванов
	Андреев
	Сидоров
	Петров

Основная задача поиска — найти запись с заданным ключом.

Все алгоритмы поиска, в зависимости от того, упорядочена таблица или нет, разбиваются по две большие группы. Упорядоченность понимается как наличие хотя бы одного отсортированного поля — а именно, ключевого.

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

Наиболее примитивный, а значит, и наименее эффективный, способ поиска— это обычный последовательный просмотр записей таблицы [9,11]. Метод применяется к таблице, организованной как массив. Предложим, что к — массив из п ключей; г — массив записей такой, что k(i) — ключ для записи r(i); key — аргумент поиска. Запишем в переменную search наименьшее целое число /, такое, что k(i) = key, если такое / существует, и -1 в противном случае.