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

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

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

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

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

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

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

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

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

Алгоритъм за двоично търсене (псевдокод)

Двоичното търсене може да се запише като кратка, итеративна рутина. То запазва два указателя, нисък и висок, и стеснява диапазона, докато целта не бъде намерена или диапазонът стане празен.

binarySearch(array, target)
    low = 0
    high = length(array) - 1
    while low <= high
        mid = (low + high) / 2      // floor value
        if array[mid] == target
            return mid
        else if array[mid] < target
            low = mid + 1
        else
            high = mid - 1
    return -1              // target not found

Рутината връща индекса на целта при успех и -1, когато стойността не е налична. Тъй като диапазонът се намалява наполовина при всяко преминаване, цикълът се изпълнява най-много log₂(n) пъти.

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

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

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

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

Пример 2

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

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

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

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

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

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

Бинарно търсене срещу линейно търсене

Бинарното търсене и линейното търсене са двата най-често срещани начина за намиране на стойност в колекция. Таблицата по-долу показва как се различават:

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

Въпроси и Отговори