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

Двоично търсене срещу линейно търсене

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

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

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

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

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

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

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