 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
Бінарний пошук
Якщо масив, у якому здійснюється пошук, упорядкований, то процес пошуку можна значно прискорити, застосувавши метод половинного ділення (бінарного пошуку). Сутність даного методу полягає у тому, що на кожному кроці частина масиву, в якій здійснюється пошук, зменшується удвічі. Ділення здійснюється до тих пір. Поки не буде знайдений елемент, або від масиву не залишиться жодного неопрацьованого елементу.
Припустимо, що масив впорядкований за зростанням. Поділимо його навпіл і порівняємо центральний елемент зі зразком пошуку. Якщо виконується рівність. Елемент знайдений. Якщо зразок більший за центральний елемент, то нижню частину масиву можна виключити з розгляду. Інакше виключається верхня частина. Далі процес поділу і аналізу продовжується. Таким чином, на кожному кроці потрібно зберігати індекси (номери) верхньої та нижньої межі частини масиву, що аналізується.
Такий пошук ще називають двійковим, або бінарним. Ще одна назва такого виду пошуку – дихотомічний (дихотомія – це поділ на дві половини).
Наприклад знайдемо X=10 у впорядкованому масиві:
Якщо вважати, що шуканий елемент знаходиться "десь усередині", спочатку перевіримо саме середній елемент: a[N div 2] = x? Якщо так, то ми знайшли, що хотіли.
 8
|
a[5] < 10
Якщо a[N div 2] < x, то i = N div 2 є замалим і шуканий елемент знаходиться "праворуч", а якщо a[N div 2] > x, то "ліворуч", тобто на номерах 1.. i. 10
|
a[7] = 10
Така перевірка фактично зменшує кількість елементів, серед яких слід шукати, вдвічі. Кожне нове ділення області пошуку ділить її навпіл. Тоді для відшукання потрібного елементу треба буде щонайбільше log2(N) перевірок. Ця пропорційність зумовлює ще одну назву описаного пошуку – логарифмічний.
Даний метод дуже ефективний, оскільки, наприклад, для масиву з 1000 елементів результат визначається навіть у гіршому випадку після 10 кроків циклу, у той час як для методів простого пошуку та пошуку з бар’єром в середньому потрібно буде 500 кроків. Однак впорядкування вихідного масиву є досить трудомісткою операцією, і вимагає часу, значно більшого, ніж проведення пошуку першими двома методами.
Таким чином, можна зробити наступні висновки: Якщо масив має невелику розмірність. То можна скористатись методом простого пошуку – постановка бар’єру істотного виграшу у швидкості не дасть. Якщо масив великий. То доцільно застосувати пошук з бар’єром. Якщо пошук проводиться багато разів в одному і тому ж масиві, то його доцільно спочатку впорядкувати, а потім застосувати бінарний пошук.
Існує кілька інших способів швидкого пошуку в масивах. Їх докладне описання є в книзі [Кнут, т.3].
Поиск по сайту: