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

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

После сравнения K и Ki мы имеем:

n K < Ki [Ri,R_i+1,..., Rn исключаются из рассмотрения],

n K = Ki [ поиск закончен],

n K > Ki [R₁,R₂,...,Ri исключаются из рассмотрения].

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