Дихотомічний пошук (двійковий пошук) Виконала Студентка 1-Апо



Дата конвертації13.04.2017
Розмір9,09 Kb.

Дихотомічний пошук (двійковий пошук)

Виконала

Студентка 1-Апо

Ільїна Олександра

План 1.Поняття дихотомічного пошуку. 2.Опис дихотомічного пошуку. 3.Опис дихотомічного пошуку на прикладі масиву. 4. Графічне представлення алгоритму. 5. Прицип роботи.

Поняття дихотомічного пошуку

  • Дихотомічний пошук (двійковий пошук) — алгоритм знаходження заданого значення у впорядкованому масиві, який полягає у порівнянні серединного елемента масиву з шуканим значенням, і повторенням алгоритму для тієї або іншої половини, залежно від результату порівняння. Зазвичай реалізується методом рекурсії, або ітерації. Основна вимога до масиву-впорядкованість.

Опис дихотомічного пошуку

  • Тепер опишемо так званий дихотомічний пошук у "нормальному словнику". Ми розкриваємо словник приблизно в його середині. Якщо слово повинно бути в словнику далі, то шукати треба лише в другій половині словника. Його середина стає для нас початком, і ми розкриваємо його на середині другої половини. Аналогічно, коли слово повинно бути в першій половині, ми залишаємо для пошуків лише її.
  • Отже, кожне заглядання в словник поділяє "простір пошуку" на дві половини й зменшує його приблизно вдвічі. Звідси й назва, оскільки дихотомія – це поділ на дві половини. Такий пошук ще називають двійковим, або бінарним.

Опис дихотомічного пошуку на прикладі масиву

В програмі буде масив від 1 до h під назвою “arr”, змінна, що позначає нижню межу пошуку, названа “k1”, верхня межа, названа “k2”, середній елемент пошуку – ”ser“; і шукане число -”x“.

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

    k2: = h;

  • Потім організовуємо цикл “повторювати доки”:
  • repeat

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

  • На кожному кроці ділимо відрізок на 2:
  • ser:= (k1+k2) div 2;

    {використовуємо функцію div, тому що ділимо без залишку}

  • Щоразу проводимо перевірку. Якщо середній менше шуканого, тоді відкидається першу половину масиву, інакше – другу:
  • if arr[ser] < x then k1:= ser +1 else k2:= ser -1

  • Так, як ми використали масив з післяумовою, вказуємо умову:
  • until (arr[ser] = x) or (k1 > k2);

  • Після чого, перевіряємо результат та, відповідно виводимо його на екран:
  • if arr[ser] = x then writeln (‘Nomer elem- ', ser)

    else writeln ('Element ne znaidenii');

    readln;

    end.

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

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

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

Так як для реалізації такого типу алгоритму пошуку потрібне попереднє сортування, то графічно зобразимо стандартне сортування методом «бульбашки».

  • Так як для реалізації такого типу алгоритму пошуку потрібне попереднє сортування, то графічно зобразимо стандартне сортування методом «бульбашки».

Графічне представлення алгоритму

Принцип роботи

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


База даних захищена авторським правом ©vaglivo.org 2016
звернутися до адміністрації

    Головна сторінка