2. Прямой поиск в упорядоченной таблице

Снимем ограничение иметь лишь последовательный доступ к таблице, при этом получим возможность эффективно использовать отношение порядка в упорядоченной таблице.

Бинарный поиск (дихотомический, логарифмический).

Суть его: сначала сравнить К со средним ключом в таблице; по результату сравнения можно определить, в какой половине таблицы продолжить поиск, применяя при этом ту же процедуру. После не более чем log₂N сравнений либо ключ будет найден, либо установлено его отсутствие.

Алгоритм В (бинарный поиск). Найти аргумент К в таблице записей R₁,R₂,…,R_n, ключи которых упорядочены по возрастанию: K₁<K₂<…<K_N. Пусть i_нач и i_кон – соответственно номера начальной и конечной записей в той области, в которой осуществляется поиск.

⌊·⌋ - целая часть (trunc).

Представим бинарный поиск в виде бинарного дерева решений. Пусть N=16. Тогда «середина» , => К₈ – ключ, соответствующий «середине» и первым (корневым) круглым узлом дерева будет 8.

Если К < К₈, то поиск проводится в левом поддереве, сравнивая К с новой «серединой» К₄ и т.д. Если К > К₈, то поиск идёт в правом поддереве.

Неудачный поиск ведёт в один из внешних квадратных узлов от 0 до N. Например, узел 6 будет достигнут тогда и только тогда, когда К₆ < К < К₇.

С помощью дерева можно доказать, что справедлива теорема:

При 2^k-1≤N≤2^k удачный поиск, использующий алгоритм В, требует минимум 1, максимум К сравнений. Неудачный поиск требует k сравнений при N=2^k-1 либо k-1 или k сравнений при 2^k-1 ≤ N <2^k-1.

Следствие: алгоритм В требует максимум [log₂N]+1 сравнений, среднее число сравнений при удачном поиске .