Разлика между двоично търсене и линейно търсене

2024 Автор: Mildred Bawerman | [email protected]. Последно модифициран: 2023-12-16 08:37

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

Линейното търсене, известно още като последователно търсене, е най-простият алгоритъм за търсене. Той търси определена стойност в списък, като проверява всеки елемент в списъка. Двоичното търсене също е метод, използван за намиране на определена стойност в сортиран списък. Методът на двоично търсене намалява наполовина броя на проверените елементи (във всяка итерация), намалявайки времето, необходимо за намиране на дадения елемент в списъка.

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

Линейното търсене е най-простият метод за търсене, който проверява последователно всеки елемент в списък, докато намери определен елемент. Входът за метода на линейно търсене е последователност (като масив, колекция или низ) и елементът, който трябва да се търси. Изходът е true, ако посоченият елемент е в рамките на предоставената последователност или false, ако не е в последователността. Тъй като този метод проверява всеки елемент от списъка, докато не бъде намерен посоченият елемент, в най-лошия случай той ще премине през всички елементи в списъка, преди да намери необходимия елемент. Сложността на линейното търсене е o (n). Следователно се счита за твърде бавен, за да се използва при търсене на елементи в големи списъци. Но това е много просто и по-лесно за изпълнение.

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

Бинарното търсене също е метод, използван за намиране на определен елемент в сортиран списък. Този метод започва чрез сравняване на търсения елемент с елементите в средата на списъка. Ако сравнението определи, че двата елемента са равни, методът спира и връща позицията на елемента. Ако търсеният елемент е по-голям от средния елемент, той отново стартира метода, използвайки само долната половина на сортирания списък. Ако търсеният елемент е по-малък от средния елемент, той отново стартира метода, използвайки само горната половина на сортирания списък. Ако търсеният елемент не е в списъка, методът ще върне уникална стойност, указваща това. Следователно бинарният метод за търсене намалява наполовина броя на сравняваните елементи (във всяка итерация), в зависимост от резултата от сравнението. Следователно,бинарното търсене се изпълнява в логаритмично време, което води до средна производителност на o (log n).

Каква е разликата между двоично търсене и линейно търсене?

Въпреки че както линейното търсене, така и бинарното търсене са методи за търсене, те имат няколко разлики. Докато двоичното търсене работи върху сортирани списъци, търсенето на линии може да работи и върху несортирани списъци. Сортирането на списък обикновено има средна сложност на n log n. линейното търсене е просто и лесно за изпълнение, отколкото бинарното търсене. Но линейното търсене е твърде бавно, за да се използва с големи списъци поради средното представяне на случая o (n). От друга страна, бинарното търсене се счита за по-ефективен метод, който може да се използва с големи списъци. Но прилагането на двоичното търсене може да бъде доста сложно и проучване показа, че точният код за двоично търсене може да бъде намерен само в пет от двадесет книги.