AlgorithmO #15 - Двоично търсене (Binary Search)

Днешният алгоритъм е изключително прост и спада към една по-различна категория алгoритми, която се нарича "разделяй и владей" (divide and conquer).

Идеята тук е, че разделяме една сложна задача на няколко по-прости, решаваме всяка една от тези по-малки задачи и накрая обединяваме решението в едно цяло.

Двоичното търсене е елементарен пример за такъв вид алгоритъм.

Трябва да кажа, че този подход е феноменален дори и извън програмирането. Аз лично го използвам почти винаги когато имам някаква тежка задача за вършене, но не искам да започна. 😃

---

ОПИСАНИЕ:

Този алгоритъм се използва за намиране на даден елемент в сортиран списък от елементи.

Двоичното търсене всъщност няма нищо общо с двоичната бройна система.

Идеята зад този алгоритъм е, че, тъй като входният ни списък е сортиран, няма нужда да сравняваме търсения елемент с всеки друг от списъка. Вместо това, можем да го сравним с елемента по средата и по този начин да разберем в коя част на масива се намира.

По този начин намаляваме значително времето за изпълнение, тъй като ограничаваме областта, в която ще търсим елемента.

Сложността му (в най-лошия случай) е O(log n), затова понякога се нарича и "логаритмично търсене".


АЛГОРИТЪМ:

1. Сравни търсения елемент с елемента по средата. *
    Ако са равни, алгоритъмът приключва.

2. Ако НЕ СА равни:
       - Ако търсеният елемент е по-малък от елемента по средата:
            - повтори стъпка 1 за подмасива преди средния елемент.
       - Ако търсеният елемент е по-голям от елемента по средата:
            - повтори стъпка 1 за подмасива след средния елемент.
   
* Елементът с индекс (L+R) / 2 (целочислено деление), където L е първият валиден индекс от масива, а R e последният валиден индекс. Без значение е дали масивът е с четен или нечетен брой елементи.

ПРИМЕР:

Нека намерим елемента със стойност 6 в следния масив:

Индекс	0	1	2	3	4	5	6	7	8	9
Стойност	-1	5	6	18	19	25	46	78	102	114

Както виждаме, масивът е сортиран и следователно можем да приложим алгоритъма за двоично търсене върху него. Колкото по-голям е един масив, толкова по-фрапиращ е ефектът на този алгоритъм.

Първо трябва да определим средния елемент. Това е елементът с индекс (L+R) / 2. Тъй кaто първият валиден индекс е 0 (L = 0) и последният 9 (R = 9), индексът на средния елемент ще е (0+9) / 2 или, иначе казано, елементът с индекс 4 (не забравяйте, че взимаме цялата част от делението).

Индекс	0	1	2	3	4	5	6	7	8	9
Стойност	-1	5	6	18	19	25	46	78	102	114

Виждаме, че този елемент има стойност 19 и 19 > 6 (търсения елемент), затова ще повторим процедурата за подмасива започващ от елемент 0 до 3 (очевидно няма да включим елемент 4, тъй като току що определихме, че е по-голям от търсения елемент):

Индекс	0	1	2	3	4	5	6	7	8	9
Стойност	-1	5	6	18	19	25	46	78	102	114

Новите граници сега са L = 0 и R = 3. От това следва, че средният елемент ще има индекс (L+R) / 2, т.е. това е елементът с индекс 1.

Индекс	0	1	2	3	4	5	6	7	8	9
Стойност	-1	5	6	18	19	25	46	78	102	114

Тъй като 5 < 6, този път отиваме надясно в подмасива състоящ се от елемент 2 до елемент 3:

Индекс	0	1	2	3	4	5	6	7	8	9
Стойност	-1	5	6	18	19	25	46	78	102	114

Сега границите са L = 2 и R = 3. Средният елемент е този с индекс 2:

Индекс	0	1	2	3	4	5	6	7	8	9
Стойност	-1	5	6	18	19	25	46	78	102	114

Супер! Виждаме, че средният елемент съвпада с елемента, който търсим. Открихме, че той има индекс 2 в масива.

Приключваме и се самопотупваме по рамото за добре свършена работа. 😀

ИМПЛЕМЕНТАЦИЯ (Java):


---

Това е за днес! Ако видите някоя грешка, кажете ми и реакцията ми ще е нещо като това. 😅