Двоично търсене срещу линейно търсене
Линейното търсене, известно още като последователно търсене, е най-простият алгоритъм за търсене. Той търси определена стойност в списък, като проверява всеки елемент в списъка. Двоичното търсене също е метод, използван за намиране на определена стойност в сортиран списък. Методът за двоично търсене намалява наполовина броя на проверените елементи (при всяка итерация), намалявайки времето, необходимо за намиране на дадения елемент в списъка.
Какво е линейно търсене?
Линейното търсене е най-простият метод за търсене, който проверява всеки елемент в списък последователно, докато намери определен елемент. Входът за метода за линейно търсене е последователност (като масив, колекция или низ) и елементът, който трябва да се търси. Изходът е вярно, ако посоченият елемент е в предоставената последователност, или невярно, ако не е в последователността. Тъй като този метод проверява всеки елемент в списъка, докато не бъде намерен посоченият елемент, в най-лошия случай той ще премине през всички елементи в списъка, преди да намери необходимия елемент. Сложността на линейното търсене е o(n). Поради това се счита, че е твърде бавен, за да се използва при търсене на елементи в големи списъци. Но това е много просто и по-лесно за изпълнение.
Какво е двоично търсене?
Двоичното търсене също е метод, използван за намиране на определен елемент в сортиран списък. Този метод започва със сравняване на търсения елемент с елементите в средата на списъка. Ако сравнението установи, че двата елемента са равни, методът спира и връща позицията на елемента. Ако търсеният елемент е по-голям от средния елемент, той стартира метода отново, като използва само долната половина на сортирания списък. Ако търсеният елемент е по-малък от средния елемент, той стартира метода отново, като използва само горната половина на сортирания списък. Ако търсеният елемент не е в списъка, методът ще върне уникална стойност, показваща това. Следователно методът за двоично търсене намалява наполовина броя на сравняваните елементи (при всяка итерация), в зависимост от резултата от сравнението. Следователно, двоичното търсене се изпълнява в логаритмично време, което води до o(log n) средна производителност на регистъра.
Каква е разликата между двоично търсене и линейно търсене?
Въпреки че както линейното търсене, така и двоичното търсене са методи за търсене, те имат няколко разлики. Докато двоичното търсене работи върху сортирани списъци, линейното търсене може да работи и върху несортирани списъци. Сортирането на списък обикновено има средна сложност на регистъра от n log n. линейното търсене е просто и лесно за изпълнение от двоичното търсене. Но линейното търсене е твърде бавно, за да се използва с големи списъци поради своята o(n) средна производителност в регистъра. От друга страна, двоичното търсене се счита за по-ефективен метод, който може да се използва с големи списъци. Но внедряването на двоично търсене може да бъде доста трудно и проучване показа, че точният код за двоично търсене може да бъде намерен само в пет от двадесет книги.
