Приклад 7.6

Розглянемо задачу пошуку в неупорядкованому масиві всіх елементів, що їх значення відповідає заданому ключу. Алгоритм розв'язання цієї задачі відрізняється від алгоритму розв'язання попередньої задачі тим, що пошук не переривається, якщо знайдено перший з потрібних елементів. Цикл завершується, коли переглянуто всі елементи масиву. Використання змінної булевого типу, яка перед виконанням циклу пошуку має значення false, а коли елемент знайдено, набуває значення true, дає можливість визначити результат пошуку. Для розв'язання цієї задачі слід замінити у програмі ех7_5 оточений пунктирними лініями цикл пошуку елемента на нижченаведений код та додати оголошення змінної f 1 ag. Модифікованій в такий спосіб програмі ех7_5 дамо назву ех7_5А.

flag: =false;
for i: =1 to n do
if a[i]=value then
begin
writeln('nom=', i);
flag: =true;
end;
if not flag then writeln('Value not found');

Рис. 7.4. Результати роботи програми ех7_5А. Пошук у неупорядкованому масиві всіх елементів, що відповідають ключу пошуку

Демонстрація прикладу

Найвідомішим методом прискорення пошуку заданого елемента в упорядкованому масиві є метод бінарного пошуку, що має також назву методу половинного ділення. Якщо масив упорядковано, то половину його елементів після порівняння шуканого значення із середнім елементом можна відкинути. Коли ці значення рівні, вважаємо, що шуканий елемент знайдено. Якщо еталонне значення менше, ніж значення середнього елемента масиву, то шуканий елемент може бути лише серед елементів лівої частини масиву, до котрої застосовується той самий метод, якщо — більше, то пошуковий метод застосовується до правої частини масиву. В результаті бінарного пошуку досліджується не більше ніж [log₂n] елементів, де n — кількість елементів масиву, а квадратними дужками позначено цілу частину числа. Тому цей метод працює значно швидше за лінійний пошук.