В последовательности записей с упорядоченными ключами K1<K2<...<KN поиск осуществляется посредством сравнения ключей. Первоначально интервал поиска Q=1, P=N. Q - левая, а P –правая гранцы интервала поиска. После каждого сравнения аргумента поиска А с ключом Ki поиск продолжается одним из следующих 3 способов:
1. Если A < Ki, то записи Xi, Xi+1,..., Xp исключаются из рас-
смотрения и поиск продолжается среди записей XQ, XQ+1,..., Xi-1, т.е.
интервал поиска сокращается и становится равным Q, P=i-1.
2. Если A = Ki, то поиск заканчивается удачно.
3. Если A > Ki, то записи XQ, XQ+1,..., Xi исключаются из рас-
смотрения и поиск производится среди записей Xi+1, Xi+2,..., Xp, т.е.
интервал поиска становится равным Q=i+1, P.
Известны следующие методы поиска: бинарный, однородный бинар-
ный, золотого сечения, интерполяционный, Фибоначчиев поиск, блоч-
ный и др., различающиеся способами выбора ключа Ki для его сравне-
ния с аргументом поиска А. При этом всегда предполагается, что
если А имеется в последовательности ключей, то K1 <= A <= KN.
Введем обозначения
|_ X_| - наибольшее целое, меньшее или равное X (целая часть).
| X | - наименьшее целое, большее или равное Х.
