(Първо публикувано на 18.01.2017)
Днешният алгоритъм е изключително прост и спада към една по-различна категория алгoритми, която се нарича “разделяй и владей” (divide and conquer).
Идеята тук е, че разделяме една сложна задача на няколко по-прости, решаваме всяка една от тези по-малки задачи и накрая обединяваме решението в едно цяло.
Двоичното търсене е елементарен пример за такъв вид алгоритъм.
Трябва да кажа, че този подход е феноменален дори и извън програмирането. Аз лично го използвам почти винаги, когато имам някаква тежка задача за вършене, но не искам да започна. 😃
ОПИСАНИЕ:
Този алгоритъм се използва за намиране на даден елемент в сортиран списък от елементи.
Двоичното търсене всъщност няма нищо общо с двоичната бройна система.
Идеята зад този алгоритъм е, че, тъй като входният ни списък е сортиран, няма нужда да сравняваме търсения елемент с всеки друг от списъка. Вместо това, можем да го сравним с елемента по средата и по този начин да разберем в коя част на масива се намира.
По този начин намаляваме значително времето за изпълнение, тъй като ограничаваме областта, в която ще търсим елемента.
Сложността му (в най-лошия случай) е O(log n), затова понякога се нарича и “логаритмично търсене”.
АЛГОРИТЪМ:
Сравни търсения елемент с елемента по средата. (*)
Ако са равни, алгоритъмът приключва.Ако НЕ СА равни:
Ако търсеният елемент е по-малък от елемента по средата,
повтори стъпка 1 за подмасива преди средния елемент.
Ако търсеният елемент е по-голям от елемента по средата,
повтори стъпка 1 за подмасива след средния елемент.
(*) Елементът с индекс (L+R) / 2 (целочислено деление), където L е първият валиден индекс от масива, а R e последният валиден индекс. Без значение е дали масивът е с четен или нечетен брой елементи.
ПРИМЕР:
Нека намерим елемента със стойност 6 в следния масив:
Както виждаме, масивът е сортиран и следователно можем да приложим алгоритъма за двоично търсене върху него. Колкото по-голям е един масив, толкова по-фрапиращ е ефектът на този алгоритъм.
Първо трябва да определим средния елемент. Това е елементът с индекс (L+R) / 2. Тъй кaто първият валиден индекс е 0 (L = 0) и последният 9 (R = 9), индексът на средния елемент ще е (0+9) / 2 или, иначе казано, елементът с индекс 4 (не забравяйте, че взимаме цялата част от делението).
Виждаме, че този елемент има стойност 19 и 19 > 6 (търсения елемент), затова ще повторим процедурата за подмасива започващ от елемент 0 до 3 (очевидно няма да включим елемент 4, тъй като току що определихме, че е по-голям от търсения елемент):
Новите граници сега са L = 0 и R = 3. От това следва, че средният елемент ще има индекс (L+R) / 2, т.е. това е елементът с индекс 1.
Тъй като 5 < 6, този път отиваме надясно в подмасива състоящ се от елемент 2 до елемент 3:
Сега границите са L = 2 и R = 3. Средният елемент е този с индекс 2:
Супер! Виждаме, че средният елемент съвпада с елемента, който търсим. Открихме, че той има индекс 2 в масива.
Приключваме и се самопотупваме по рамото за добре свършена работа. 😀
ИМПЛЕМЕНТАЦИЯ (Java):
—
Това е за днес! Ако видите някоя грешка, кажете ми и реакцията ми ще е нещо като това. 😅