БІНАРНИЙ ПОШУК

Методи пошуку в відсортованих таблицях покажчиків засновані на алгоритмі бінарного пошуку

Нехай впорядкований масив х з п елементів містить значення

5 7 11 18 26 32 44 57 81 90 94 97 107 116 129 147 179 і нехай заданий аргумент пошуку ключ,рівний, наприклад, 129

Ідея алгоритму бінарного пошуку така:

• порівняти аргумент пошуку ключ зі значенням середнього елемента х [середовищ]масиву х,

де середовищ = [П / 2], а [з] ціла частина числа с

• якщо вони рівні, то пошук завершено, інакше, якщо ключ < х [середовищ], виконати аналогічним чином пошук в позиціях масивух,попередніх позиції середовищ, в іншому випадку, якщо ключ> х [середовищ], виконати аналогічним чином пошук в позиціях масиву х, Наступних за позицією середовищ

Виключити з подальшого розгляду частина масиву дозволяє той факт, що масив впорядкований

Проілюструємо процес бінарного пошуку Число елементів масиву п = 17, тоді[П / 2] = 8 Тому спочатку виконується порівняннясередовищзx 8 = 57 Так яксередовищ> x8, то зона пошуку на наступному кроці обмежується ділянкою від 9-го елемента до 17-го Ця ділянка складається з девяти елементів і його серединою є елемент х13= 107 ([(9 + 17) / 2] = 13) Оскільки середовищ> x13, то зона пошуку обмежується ділянкою від 14-го до 17-го елементу Його серединою є елементx15   На цьому процес пошуку завершений, так якх15 = середовищВідобразимо на рис 93 процес пошуку елемента ключ = 129, виділяючи у вигляді підкреслення на кожному кроці зони пошуку

Ітерація 0

5 7 11 18 26 32 44 57 81 90 94 97 107 116 129 147 179

Ітерація 0

5 7 11 18 26 32 44 57 81 90 94 97 107 116 129 147 179

Ітерація 1

5 7 11 18 26 32 44 57 81 90 94 97 107 116 129 147 179

Ітерація 3

5 7 11 18 26 32 44 57 81 90 94 97 107 116 129 147 179

Рис 93 Приклад дихотомії

Кожне порівняння зменшує число можливих кандидатів у 2 рази Максимальне число кроків пошуку буде в тому випадку, коли аргумент пошуку знаходиться на початку або в кінці масиву У цьому випадку буде потрібно log2n + 1 ітерацій Дійсно, якщо число елементів у масиві дорівнює п = 2т, ключ буде знайдений, коли нерозглянутим залишиться тільки один елемент, тобто через т кроків У свою чергу, при заданому п маємо т = log2n Після аналізу останнього елемента отримуємо загальне число ітерацій log2n + 1 Тому обчислювальна складність бінарного пошуку складає O (log2n)

Однак наведений алгоритм не дозволяє в загальному випадку точно вирішити завдання пошуку, коли файл або масив містять повторювані значення ключів Розглянемо, наприклад, масив

5  7  11  18  26  32  44  57  81  90  94  97  107  129  129  147  179

в якому елемент (Ключ)129 міститься 2 рази Тоді, якщо аргумент пошуку буде дорівнює 129, алгоритм, як і колись, вкаже, що ключ знаходиться в 15-й позиції, тобто буде знайдено не перше, а друге значення ключа 129 (перше значення ключа розташоване в позиції 14) У ряді випадків ця помилка принципова, тоді вона усувається в результаті очевидною модифікації алгоритму бінарного пошуку

922&nbsp&nbsp&nbsp&nbsp ПОРІВНЯННЯ ПОСЛІДОВНОГО І бінарного пошуку

Нехай файл, в якому виконується пошук, відсортований і містить 1024 (210) елемента У разі послідовного пошуку найбільше число ітерацій дорівнюватиме 1024, а бінарного 11 Тобто різниця в два порядки

Порівняємо тепер тимчасові витрати на пошук в разі не відсортованого файлу При послідовному пошуку максимальне число ітерацій, зрозуміло, зберігається Бінарний пошук непридатний Виконаємо, однак, швидку сортування файлу У середньому для цього буде потрібно 1024 * log21024 = 10240 ітерацій Далі виконаємо бінарний пошук, на який буде витрачено не більше 11 ітерацій

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

Джерело: Бартеньев О В 1С: Підприємство: програмування для всіх Базові обєкти та розрахунки на одній дискеті М: Діалог-МІФІ, 2005 464 с

Схожі статті:


Сподобалася стаття? Ви можете залишити відгук або підписатися на RSS , щоб автоматично отримувати інформацію про нові статтях.

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*