Двоичното търсене е най-известната техника за търсене в света на програмирането. Значителното предимство на двоичното търсене е, че е по-бързо от линейния метод на търсене. И така, нека поговорим за неговия алгоритъм.
Алгоритъм:
Първото важно нещо в двоичното търсене е масивът, върху който се прилага двоично търсенетрябва да бъде сортиран масив. Двоичното търсене няма да работи с несортирания масив.
В двоичен код първо сравняваме средния елемент на масива с елемента, който трябва да бъде намерен. Ако средният елемент и целевият елемент са еднакви, тогава просто върнете средния индекс. Ако не са еднакви, проверете дали целевата стойност е по-голяма или по-малка от средния елемент.
Ако целевият елемент е по-малък от средния елемент, ние се придвижваме към лявата част на масива или ако е по-голям от средния елемент, тогава се придвижваме към дясната част на масива. Тъй като списъкът е сортиран, така че целевият елемент не може да бъде от другите страни на масива в зависимост от сравнението със средния елемент.
След това го сравняваме със средния елемент на тази част и правим същата процедура, докато елементът бъде намерен, или ако се свием до размера само на един елемент и в този случай просто връщаме -1, което означава целта елемент не е намерен.
Анализ:
Както казах по-рано Двоичното търсене е по-бързо от линейното търсене, защото просто нарязва масива и стеснява частта за търсене.
Така че в най-добрия случай времевата сложност на двоичното търсене е O(1), а в най-лошия случай неговата времева сложност е O(log n), което е много по-малко от времевата сложност на линейното търсене O(n).
код:
Ето кода за рекурсивно и итеративно двоично търсене в C++.
