Алгоритъм за двоично търсене с ПРИМЕР

Преди да научим двоично търсене, нека научим:

Какво е търсене?

Търсенето е помощна програма, която позволява на потребителя да намира документи, файлове, медии или друг тип данни, съхранявани в база данни. Търсенето работи на простия принцип на съпоставяне на критериите със записите и показването им на потребителя. По този начин работи най-основната функция за търсене.

Какво е двоично търсене?

Двоичното търсене е усъвършенстван тип алгоритъм за търсене, който намира и извлича данни от сортиран списък с елементи. Неговият основен принцип на работа включва разделяне на данните в списъка наполовина, докато необходимата стойност бъде локализирана и показана на потребителя в резултата от търсенето. Двоичното търсене е известно като a полуинтервално търсене или логаритмично търсене.

Как работи двоичното търсене?

Двоичното търсене работи по следния начин:

Процесът на търсене започва с намиране на средния елемент на сортирания масив от данни
След това ключовата стойност се сравнява с елемента
Ако ключовата стойност е по-малка от средния елемент, тогава търсенето анализира горните стойности към средния елемент за сравнение и съвпадение
В случай че ключовата стойност е по-голяма от средния елемент, тогава търсенето анализира по-ниските стойности на средния елемент за сравнение и съвпадение

Примерно двоично търсене

Нека разгледаме примера на речник. Ако трябва да намерите определена дума, никой не преминава през всяка дума по последователен начин, а произволно намира най-близките думи, за да търси необходимата дума.

Горното изображение илюстрира следното:

Имате масив от 10 цифри и елементът 59 трябва да бъде намерен.
Всички елементи са маркирани с индекс от 0 до 9. Сега се изчислява средата на масива. За да направите това, вземате най-лявата и дясната стойност на индекса и ги разделяте на 2. Резултатът е 4.5, но ние вземаме долната стойност. Следователно средата е 4.
Алгоритъмът изпуска всички елементи от средата (4) до най-ниската граница, тъй като 59 е по-голямо от 24, и сега масивът остава само с 5 елемента.
Сега 59 е по-голямо от 45 и по-малко от 63. Средната е 7. Следователно стойността на десния индекс става средна – 1, което е равно на 6, а стойността на левия индекс остава същата като преди, която е 5.
В този момент знаете, че 59 идва след 45. Следователно левият индекс, който е 5, също става среден.
Тези итерации продължават, докато масивът се намали само до един елемент или елементът, който трябва да бъде намерен, стане средата на масива.

Пример 2

Нека да разгледаме следния пример, за да разберем как работи двоичното търсене

Имате масив от сортирани стойности, вариращи от 2 до 20 и трябва да намерите 18.
Средната стойност на долната и горната граница е (l + r) / 2 = 4. Стойността, която се търси, е по-голяма от средната, която е 4.
Стойностите на масива, по-малки от средната, се изпускат от търсенето и се търсят стойности, по-големи от средната стойност 4.
Това е повтарящ се процес на разделяне, докато се намери действителният елемент, който ще се търси.

Защо се нуждаем от двоично търсене?

Следните причини правят двоичното търсене по-добър избор за използване като алгоритъм за търсене:

Двоичното търсене работи ефективно върху сортирани данни, независимо от размера на данните
Вместо да извършва търсене чрез преминаване през данните в последователност, двоичният алгоритъм получава случаен достъп до данните, за да намери необходимия елемент. Това прави циклите на търсене по-кратки и по-точни.
Двоичното търсене извършва сравнения на сортираните данни въз основа на принципа на подреждане, отколкото чрез сравнения на равенство, които са по-бавни и най-вече неточни.
След всеки цикъл на търсене алгоритъмът разделя размера на масива наполовина, следователно при следващата итерация ще работи само в останалата половина на масива

Научете следващия ни урок за Линейно търсене: Python, C++ Пример

Oбобщение

Търсенето е помощна програма, която позволява на потребителя да търси документи, файлове и други видове данни. Двоичното търсене е усъвършенстван тип алгоритъм за търсене, който намира и извлича данни от сортиран списък с елементи.
Двоичното търсене е известно като търсене с половин интервал или логаритмично търсене
Работи, като разделя масива наполовина при всяка итерация под желания елемент.
- двоичен алгоритъм взема средата на масива, като разделя сумата от стойностите на най-левия и най-десния индекс на 2. Сега алгоритъмът изпуска или долната, или горната граница на елементите от средата на масива, в зависимост от елемента, който трябва да бъде намерен.
Алгоритъмът получава произволен достъп до данните, за да намери необходимия елемент. Това прави циклите на търсене по-кратки и по-точни.
Двоичното търсене извършва сравнения на сортираните данни въз основа на принципа на подреждане, вместо да използва сравнения на равенство, които са бавни и неточни.
Двоичното търсене не е подходящо за несортирани данни.