Преди да научим двоично търсене, нека научим:
Какво е търсене?
Търсене е помощна програма, която позволява на потребителя да намира документи, файлове, носители или друг вид данни, съхранявани в база данни. Търсене работи по простия принцип на съвпадение на критериите със записите и показването им на потребителя. По този начин работи най-основната функция за търсене.
Какво е двоично търсене?
Двоичното търсене е усъвършенстван тип алгоритъм за търсене, който намира и извлича данни от сортиран списък с елементи. Основният му принцип на работа включва разделяне на данните в списъка наполовина, докато необходимата стойност бъде намерена и показана на потребителя в резултата от търсенето. Бинарното търсене е широко известно като търсене с половин интервал или логаритмично търсене .
В този урок за алгоритъм ще научите:
- Какво е търсене?
- Какво е двоично търсене?
- Как работи двоичното търсене?
- Пример за двоично търсене
- Защо се нуждаем от двоично търсене?
Как работи двоичното търсене?
Двоичното търсене работи по следния начин:
- Процесът на търсене се инициира чрез намиране на средния елемент на сортирания масив от данни
- След това ключовата стойност се сравнява с елемента
- Ако стойността на ключа е по-малка от средния елемент, тогава търсенията анализират горните стойности към средния елемент за сравнение и съвпадение
- В случай, че стойността на ключа е по-голяма от средния елемент, тогава търсенията анализират по-ниските стойности към средния елемент за сравнение и съвпадение
Пример за двоично търсене
Нека разгледаме примера на речник. Ако трябва да намерите определена дума, никой не преминава през всяка дума последователно, но произволно намира най-близките думи, за да търси необходимата дума.
Горното изображение илюстрира следното:
- Имате масив от 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.
- Това е повтарящ се процес на разделяне, докато не бъде намерен действителният елемент, който ще се търси.
Защо се нуждаем от двоично търсене?
Следните причини правят бинарното търсене по-добър избор, който да се използва като алгоритъм за търсене:
- Двоичното търсене работи ефективно върху сортирани данни, независимо от размера на данните
- Вместо да извърши търсенето чрез преминаване през данните в последователност, двоичният алгоритъм извършва произволен достъп до данните, за да намери необходимия елемент. Това прави циклите на търсене по-кратки и по-точни.
- Двоичното търсене извършва сравнения на сортираните данни въз основа на принцип на подреждане, отколкото използването на сравнения на равенствата, които са по-бавни и най-вече неточни.
- След всеки цикъл на търсене алгоритъмът разделя размера на масива наполовина, следователно в следващата итерация той ще работи само в останалата половина на масива
Обобщение
- Търсене е помощна програма, която позволява на потребителя да търси документи, файлове и други видове данни. Двоичното търсене е усъвършенстван тип алгоритъм за търсене, който намира и извлича данни от сортиран списък с елементи.
- Бинарното търсене е известно като търсене с половин интервал или логаритмично търсене
- Той работи чрез разделяне на масива наполовина на всяка итерация под необходимия елемент е намерен.
- Двоичният алгоритъм взема средата на масива, като разделя сумата от лявата и най-дясната стойност на индекса на 2. Сега алгоритъмът изпуска или долната, или горната граница на елементите от средата на масива, в зависимост от елемента, който трябва да бъде намерен .
- Алгоритъмът получава произволен достъп до данните, за да намери необходимия елемент. Това прави циклите на търсене по-кратки и по-точни.
- Двоичното търсене извършва сравнения на сортираните данни въз основа на принцип на подреждане, отколкото използването на сравнения на равенство, които са бавни и неточни.
- Двоичното търсене не е подходящо за несортирани данни.