 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
Метод пошуку з бар’єром
Перевагою методу простого пошуку є його простота та наочність. Недоліком методу є те, що у заголовку циклу доводиться здійснювати дві перевірки: на допустимість індексу і на рівність значення. Якби ми знали, що шукане значення точно є десь у масиві, то першу перевірку на кінеці масиву можна було б не вказувати, що прискорило б пошук.
Це наштовхує на думку, що у вихідний масив потрібно тимчасово включити шукане значення. Однак, оскільки розміри масиву змінені бути не можуть, включення можна здійснити на останнє місце масиву. Тоді після завершення пошуку потрібно повернути в кінець масиву початкове значення. Для одержання результату пошуку потрібно перевірити, чи дорівнює шукане значення тому елементу масиву, на якому відбулось завершення роботи алгоритму. Навіть, якщо елемент у початковому масиві був відсутній, і зупинка була здійснена на включеному в масив зразкові, перевірка результату буде проведена для вихідного елементу масиву, який на той час замінить зразок пошуку. Наведений метод називається “пошук елементу з бар'єром”. Роль бар’єрного елементу виконує включений в масив зразок пошуку.
Включення повинно здійснюватись замість останнього елементу масиву, після якого інших елементів немає.
Наприклад: Шукаємо x=7
an = a[n]
a[n] = x
 7
|
Знайшли i=6
Шукаємо x=9
an = a[n]
a[n] = x
 9
|
Знайшли i= n
Перевіряємо a[n] = 9? => ні, отже такого елемента немає в масиві
Додаткові операції по установці і зняттю бар'єра окупаються спрощенням циклу, у якому витрачається основний час при пошуку. Особливо це позначиться при великих розмірах масиву. В загальному випадку час пошуку буде меншим, ніж у попередньому випадку.
Звичайно у тому випадку, коли елементи масиву можуть повторюватись пошук не можна припиняти поки не перевірили всі елементи масиву до кінця.
 5
|  5
|  5
|
Тоді для практичної реалізації алгоритму потрібно застосувати цикл з лічильником, а пошук проводити до кінця масиву, це дасть можливість знайти всі відповідні елементи. У такому випадку кількість перевірок дорівнює - N.
Поиск по сайту: