Съдържание:
Определение - Какво означава двоично търсене?
Използва се двоичен алгоритъм за търсене, за да се намери позицията на конкретна стойност, съдържаща се в сортиран масив. Работейки с принципа на разделяне и завладяване, този алгоритъм за търсене може да бъде доста бърз, но предимството е, че данните трябва да бъдат в подредена форма. Той работи като стартира търсенето в средата на масива и работи надолу по първата долна или горна половина на последователността. Ако средната стойност е по-ниска от целевата стойност, това означава, че търсенето трябва да отиде по-високо, ако не, то трябва да погледне на низходящата част на масива.
Двоичното търсене е известно още като полуинтервално търсене или логаритмично търсене.
Техопедия обяснява Бинарно търсене
Бинарното търсене е бърз и ефективен метод за намиране на конкретна целева стойност от набор от подредени елементи. Стартирайки в средата на сортирания списък, той може ефективно да намали пространството за търсене наполовина, като определи дали да се изкачи или да се спусне списъка въз основа на средната стойност в сравнение с целевата стойност.
Например с целева стойност 8 и пространство за търсене от 1 до 11:
- Средната / средната стойност е намерена и показалеца е зададен там, което в този случай е 6.
- Целта на 8 се сравнява с 6. Тъй като 6 е по-малка от 8, целта трябва да бъде в по-горната половина.
- Показалецът се премества към следващата стойност (7) и се сравнява с целта. Той е по-малък, следователно показалеца се премества към следващата по-висока стойност.
- Показалецът вече е на 8. Сравняването на това с целта е точно съвпадение, следователно целта е намерена.
Използвайки двоично търсене, целта трябваше да се сравнява само с три стойности. В сравнение с линейното търсене, той щеше да започне от първата стойност и да се премести нагоре, като се наложи да се сравни целта с осем стойности. Двоично търсене е възможно само с подреден набор от данни; ако данните са подредени на случаен принцип, тогава линейното търсене ще доведе до резултати през цялото време, докато бинарното търсене вероятно ще бъде заседнало в безкраен цикъл.
