Сравнение последовательного и бинарного поиска в VFP

Пусть файл, в котором выполняется поиск, отсортирован и содержит 1024 (2¹⁰) элемента. В случае последовательного поиска наибольшее число итераций будет равно 1024, а бинарного – 11. То есть разница в два порядка.

Сравним теперь временные затраты на поиск в случае неотсортированного файла. При последовательном поиске максимальное число итераций, разумеется, сохраняется. Бинарный поиск неприменим. Выполним, однако, быструю сортировку файла. В среднем для этого потребуется 1024*log₂1024 = 10240 итераций. Далее выполним бинарный поиск, на который будет затрачено не более 11 итераций.

Приведенные цифры позволяют сделать вывод: если файл неотсортирован и в процессе вычислений задача поиска в файле возникает сравнительно редко (в нашем примере не более 10 раз), то можно применять последовательный поиск, в противном случае более целесообразно прежде отсортировать файл и при вычислениях применять бинарный поиск.

По очевидным причинам сортировка файла заменяется его индексированием. Записи каждого созданного индекса упорядочены по значениям индексного выражения в возрастающем или убывающем порядке.