Бінарний пошук - один з найпростіших способів знаходження елемента в масиві

Досить часто програмісти, навіть початківці, стикаються з тим, що є набір чисел, в якому необхідно знайти певне число. Ось цю колекцію називають масивом. А щоб знайти потрібний елемент в ньому, є величезна безліч способів. Але найпростішим серед них по праву можна вважати бінарний пошук. У чому ж полягає даний метод? І як реалізувати бінарний пошук? Паскаль є найпростішою середовищем для організації такої програми, тому будемо використовувати саме його для вивчення.

Спочатку розберемо, в чому переваги цього методу, адже так ми зможемо зрозуміти, який сенс у вивченні даної теми. Отже, припустимо, є масив з розмірністю хоча б 100000000 елементів, в якому потрібно знайти певний. Звичайно, це завдання легко можна вирішити простим лінійним пошуком, при якому ми з допомогою циклу будемо порівнювати шуканий елемент з усіма тими, що є в масиві. Проблема в тому, що реалізація цієї ідеї буде займати занадто багато часу. У простій паскалевской програмі на кілька процедур і з трьома рядками основного тексту ви цього не помітите, але коли приступите до більш-менш великим проектам з великою кількістю розгалужень і непоганим функціоналом, готова програма буде грузиться дуже довго. Особливо в тому випадку, якщо у комп`ютера буде слабка працездатність. Тому й існує бінарний пошук, який скорочує час пошуку як мінімум удвічі.

Отже, в чому ж полягає принцип роботи даного методу? Відразу варто сказати, що працює бінарний пошук не в будь-якому масиві, а тільки в відсортованому наборі чисел. На кожному наступному кроці береться середній елемент масиву (мається на увазі за номером елемента). Якщо шукане число більше середнього, значить все те, що знаходиться ліворуч, тобто менше середнього елемента, можна відкинути і не шукати там. І навпаки, якщо менше середнього - серед тих чисел, що праворуч, можна не шукати. Далі виберемо нову область пошуку, де першим елементом стане середній елемент всього масиву, а останній так і залишиться останнім. Середнім же числом нової області стане frac14- всього відрізка, тобто (останній елемент + середній елемент всього масиву) / 2. Знову проводиться та ж операція - порівняння з середнім числом масиву. Якщо шукана величина менше середнього, відкидаємо праву частину, і так само робимо далі, поки ось цей середній елемент не виявиться шуканим.

Звичайно, найкраще подивитися на прикладі, як пишеться бінарний пошук. Pascal тут підійде будь - версія не важлива. Напишемо просту програму.

У ній буде масив від 1 до h під назвою "massiv", змінна, що позначає нижню межу пошуку, названа "niz", верхня межа, названа "verh", середній елемент пошуку - "sredn" - і шукане число - "isk".

Отже, спочатку призначаємо верхню і нижню межі інтервалу пошуку:

niz: = 1
verh: = h + 1-

Потім організовуємо цикл "поки нижня менше верхньої межі":

While niz < verh - 1 do
begin

На кожному кроці ділимо відрізок на 2:

sredn: = (niz + verh) div 2 {використовуємо функцію div, бо ділимо без залишку}

Кожен раз проводимо перевірку. Якщо середній дорівнює шуканого, перериваємо цикл, так як необхідний елемент вже знайдений:

іf sredn = isk then break-

Якщо середній елемент масиву більше шуканого, відкидаємо ліву частину, тобто верхньою межею призначаємо середній елемент:

if massiv [sredn]> isk then verh: = sredn-

А якщо навпаки, то його робимо нижньою межею:

else niz: = sredn-
end-

От і все, що буде в програмі.

Розберемо, як виглядатиме бінарний метод на практиці. Візьмемо такий масив: 1, 3, 5, 7, 10, 12, 18 і будемо шукати в ньому число 12.

Всього у нас 7 елементів, тому середнім будемо четвертий, його значення 7.

Так як 12 більше 7, елементи 1,3 і 5 ми можемо відкинути. Далі у нас залишилося 4 числа, 4/2 без залишку дорівнює 2. Значить, новим середнім елементом буде 10.

Так як 12 більше 10, відкидаємо 7. Залишається тільки 10, 12 і 18.

Тут середній елемент вже 12, це і є шукане число. Завдання виконано - число 12 знайдено.