Поиск данных

Метод последовательного перебора.

Последовательный метод поиска называют также методом последовательного перебора. Это самый универсальный, наиболее простой и самый длительный 
метод поиска. В процессе поиска осуществляется последовательное обращение к каждой записи массива и при этом определяется, удовлетворяет ли данная 
запись критерию выдачи.

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

В алгоритме учтем два возможных варианта результата: 1) искомые данные найдены; и 2) искомые данные не найдены. Результаты поиска нередко оказываются отрицательными, если в наборе нет искомых данных.

Метод половинного деления.

Возьмем для примера игру в угадывание целого числа в определенном 
диапазоне. Например, от 1 до 128. Один играющий загадывает число, второй пытается его угадать, задавая вопросы, на которые ответом может быть «да» или «нет». Ключом поиска в этом случае является число, а критерием поиска — совпадение числа, задуманного первым игроком, с числом, называемым вторым игроком.
Если вопросы задавать такие: «Число равно единице?». Ответ: «Нет». Вопрос: «Число равно двум?» и т. д., то это будет последовательный перебор. Среднее число вопросов при многократном повторении игры с загадыванием разных 
чисел из данного диапазона будет равно 128/2 = 64.
Однако поиск можно осуществить гораздо быстрее, если учесть упорядоченность натурального ряда чисел, благодаря чему между числами действуют отношения больше или меньше.
Так же надо искать и одно число из 128. Первый вопрос: «Число меньше 65?» — «Да!» — «Число больше 32?» — «Нет!» и т. д. Любое число угадывается 
максимум за 7 вопросов. Это связано с тем, что 128 = 2'. Снова работает главная формула информатики.
Метод половинного деления для упорядоченного набора данных работает 
гораздо быстрее (в среднем), чем метод последовательного перебора.
На рис. 2.8 наглядно показан процесс поиска (угадывания) числа «3» из 
диапазона целых чисел от 1 до 8.



Если максимальное число диапазона N не равно целой степени двойки, то оптимальное количество вопросов не будет постоянной величиной, а будет равно одному из двух значений: X или Х+1, где
2^х < N < 2^x+1.
Например, если число ищется в диапазоне от 1 до 7, то его можно угадать за 2 
или 3 вопроса, поскольку
2² < 7 < 2³.
Число из диапазона от 1 до 200 можно угадать за 7 или 8 вопросов, поскольку
2⁷ < 200 < 2⁸.
Проверьте эти утверждения экспериментально.
Половинным делением можно искать, например, нужную страницу в толстой 
книге: открыть книгу посередине, понять, в какой из половин находится искомая страница. Затем открыть середину этой половины и т. д.
Набор данных может быть упорядочен не только по числовому ключу. Другой вариант упорядочения — по алфавиту. Половинным делением можно 
осуществлять поиск в орфографическом словаре или в словаре переводов слов с иностранного языка.