Двійковий пошук

Матеріал з Словник з інформатики
Перейти до: навігація, пошук

Поняття та означення двійкового пошуку

Двійковий пошук — це алгоритм, який використовується для пошуку заданого елементу у відсортованому масиві, який полягає у порівнянні серединного елемента масиву з шуканим значенням, і повторенням алгоритму для тієї або іншої половини, залежно від результату порівняння. Трудомісткість алгоритму , де n — кількість елементів у масиві. У процесі розв’язування практичних задач особливо часто пошук і впорядкування здійснюються в трьох класах даних: лінійних списках, масивах і таблицях.

Методи впорядкування даних

Із різноманітних методів впорядкування даних виділимо найпростіші, які широко застосовуються в процесі розв’язування практичних задач, а саме: метод впорядкування вибором; метод попарної перестановки; метод сортування “ бульбашки ”. Сутність методу впорядкування вибором: у послідовності знаходиться максимальний елемент. Максимальний елемент і крайній правий елемент міняються місцями. Після цього правий крайній елемент з подальшого розгляду виключається. Суть методу попарної перестановки (послідовність потрібно розмістити в порядку зростання її елементів): послідовність розглядається зліва направо. При цьому порівнюються елементи і т.д. Близьким до методу попарної перестановки є метод сортування “бульбашки”. Його сутність: перший елемент послідовності поступово порівнюється з елементами, що знаходяться справа від нього. Якщо елемент справа менший за перший, то вони міняються місцями.

Використання двійкового пошуку

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

Перелік використаних джерел

двійковий пошук методи пошуку