Лекция: Принцип методу упорядкування обміном

Зліва направо по черзі порівнюються два сусідні елементи (перший з другим, другий з третім і т.д.), і якщо їх взаємне розміщення не відповідає критерію впорядкування, то вони переставляються місцями.

Після першого перегляду на останній n-й позиції масиву буде знаходитися найбільший елемент. Тому другий перегляд виконується до n-1–го елемента. Третій – до n-2–го елемента і т.д. Всього потрібно n-1 перегляд.

Алгоритм бінарного пошуку використовується для знаходження заданого елемента у впорядкованому масиві. Розглянемо його на прикладі масиву, впорядкованого за зростанням.

Принцип бінарного пошуку:

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

Так продовжують до тих пір, поки або елемент буде знайдено, або довжина зони пошуку стане рівна нулю. В останньому випадку шуканий елемент не буде знайдено.

Застосуємо алгоритм бінарного пошуку для знаходження числа X = 14 у масиві A.

Отже, шуканий елемент масиву має номер 5.

Лабораторне заняття №3