Двійковий пошук
Матеріал з Вікіпедії — вільної енциклопедії.
Двійкóвий пóшук — алгоритм знаходження заданого значення у впорядкованому масиві, який полягає у порівнянні серединного елемента масиву з шуканим значенням, і повторенням алгоритму для тієї або іншої половини (див. двійкове дерево пошуку), залежно від результату порівняння.
Трудомісткість алгоритму 1 + log2N.
Зміст |
[ред.] Цікаві дані
[ред.] Масове використання лінійного пошуку
Двійковий пошук суттєво швидший за лінійний, відносно простий в реалізації і загальновживаний. Проте в реальних програмах трапляються випадки використання лінійного пошуку, що мають наслідком суттєві проблеми зі швидкодією. Так, в серйозній науковій публікації Communications of the ACM "TWA Reservation system" є такий шматок:
Ми мали програму, яка робила лінійний пошук у дуже великому масиві майже 100 раз на секунду. ... Ми відстежили проблему до лінійного пошуку, замінили його на двійковий, і проблема зникла
який Джон Бентлі у книзі «Перлини програмування» назвав анекдотом і повідомив, що бачив цю саму історію у багатьох системах. Опублікована на сайті Borland стаття описує проблеми швидкодії, викликані реалізацією певних процедур роботи з базами даних у VCL, які по суті зводяться до використання лінійного пошуку замість двійкового.
[ред.] Помилки в реалізації
В тій же книзі Джон Бентлі використовує двійковий пошук як приклад упродовж розділу присвяченого тестуванню та відлагодженню. Він наводить типову невірну реалізацію двійкового пошуку, поширену, за його словами, серед професійних програмістів. Невірний код відрізняється від наведеного далі прикладу рядками
right=mid;
та
else left=mid;
Такий код призводить до нескінченного циклу для багатьох значень шуканого елемента, наприклад, при спробі знайти найбільший елемент масиву.
За спогадами відомого програмового інженера Джошуа Блоха (Joshua Bloch), йому запала в пам'ять лекція з курсу алгоритмів у Карнегі Мелон Юнівеситі, на якій Джон Бентлі попросив майбутніх кандидатів наук написати двійковий пошук, і розібрав невірний варіант, яких було більшість.
Сам Джошуа є автором реалізації бібліотечної функції двійкового пошуку у Java від Sun. У 2006 році він був шокований іще раз, коли довідався, що ретельно розібрана у Бентлі реалізація, та його власна, яка 9 років знаходилась у бібліотеці Java, містить ще одну помилку. Одна програма, що обробляла великий набір данних, падала через наступний рядок у реалізації
int mid = (low + high) / 2;
Причиною було те, що low і high були великими, і їх сума викликала переповнення типу int, приводячи до від'ємного значення mid. Таким чином, для обробки великих масивів необхідно писати в реалізації на Java
int mid = low + ((high - low) / 2);
чи
int mid = (low + high) >>> 1;
Хоча ця проблема виявлена у Java, вона не є її відмінністю, така сама помилка присутня, наприклад, у реалізаціях бібліотечної функції bsearch у Сі.
