Add pract04

1 files changed, 224 insertions, 0 deletions

diff --git a/Practicum/pract04/readme.md b/Practicum/pract04/readme.md
new file mode 100644
index 0000000..2c62cff
--- /dev/null
+++ b/Practicum/pract04/readme.md
@@ -0,0 +1,224 @@
+# Практикум №4 по Структури от данни, спец. ИС
+
+Какво представляват алгоритмите за търсене? Може би е интуитивно, но те представляват методи или процедури, 
+използвани за намиране на конкретен елемент в дадена колекция от данни. Ще се запознаем с няколко по-известни от тях. 
+
+## Линейно търсене 
+Когато търсим елемент в дадена колекция, нещото, което ни хрумва първо, е да я обходим цялата и да проверим дали той е в нея. 
+Съответно, ако го намерим, искаме да върнем позицията му. Цялата тази идея е имплементирана именно в алгоритъма `Linear Search` или линейно търсене на български.
+Нека разгледаме примерна имплементация:
+
+```c++
+template <class T> 
+int linear_search(const std::vector<T>& data, const T& el)
+{
+    for (int i = 0; i < data.size(); i++)
+    {
+        if (data[i] == el)
+            return i;
+    }
+
+    return -1;
+}
+```
+
+Както можем да видим, алгоритъма обхожда цялата колекция и в най-лошия случай ще направи **n** стъпки, т.е. сложността му в `worst-case` е **O(n)**. 
+В `average-case` ще направи *n/2* стъпки, тъй като предполагаме, че тогава търсеният елемент ще се намира в средата на колекцията, т.е. сложността отново е **O(n)**. 
+Съответно `best-case` ще ни е, когато елементът се намира в началото на колекцията, т.е. сложността е константна - **O(1)**.
+
+Хубавото на този алгоритъм е, че не изисква допълнително сортиране на елементите, което явно ще увеличи сложността му.  
+
+Но дали има начин да оптимизираме този алгоритъм? 
+
+Ако се замислим, сложността му няма как да бъде оптимизирана - винаги имаме обхождане на елементите на масива.
+
+Но какво друго можем да направим? Ако погледнем, ще видим, че на всяка стъпка извършваме 2 проверки - за елемента и за индекса i дали не е излезнал извън границите на нашата колекция.
+Всъщност можем да направим така, че да спестим втората проверка. Как? Ами като сложим търсения елемент в края на нашата колекция на мястото на последния елемент. 
+Тази техника се нарича добавяне на `sentinel` в края на колекцията и е често срещана в практическата сфера.
+Нека видим как бихме могли да го имплементираме:
+
+```c++
+template <class T> 
+int linear_search_sentinel(const std::vector<T>& data, const T& el)
+{
+    T last = data.back();
+    data.back() = el;
+
+    int i = 0;
+    while (el != data[i])
+    {
+        i++;
+    }
+    
+    data.back() = last;
+
+    if(i < data.size() - 1 || data.back() == el)
+        return i;
+
+    return -1;
+}
+```
+
+Както виждаме, сложността си остава същата и в трите случая, но проверките ни драстично намаляват, което за по-обемни колекции ще е от голямо значение.
+
+## Binary Search
+Разгледахме вече случая, в който обхождаме цялата колекция. Както сами се убедихме, той не е много оптимален (особено за големи колекции), тъй като ще се наложи да ги обхожда целите.
+Нека се замислим - ако елементите ни са в сортиран вид, няма ли по-оптимален начин да намерим търсения от нас такъв? Отговорът е - да, има, и се нарича `Binary Search` или двоично търсене на български.
+
+Идеята му е да вземем средния елемент на колекцията. Той я разделя на две половини - лява и дясна.
+Първо ще сравним търсения със средния елемент - ако са равни, значи сме го открили и можем да върнем неговата позиция. Ако не са равни, ще направим следното:
+тъй като колекцията ни е сортирана, ако търсеният елемент е по-голям от средния, значи се намира в дясната половина, а ако е по-малък - съответно в лявата. По този начин ще приложим същото
+търсене върху половината, в която вече сме сигурни, че се намира нашия елемент и така, докато не стигнем до него.
+
+Нека разгледаме как бихме могли да имплементираме алгоритъма:
+
+```c++
+template <class T>
+int binary_search(const std::vector<T>& data, T el)
+{
+    int beg = 0, end = data.size() - 1;
+
+    while (beg <= end)
+    {
+        int mid = beg + (end - beg) / 2;
+
+        if (data[mid] == el)
+            return mid;
+
+        if (el < data[mid])
+            end = mid - 1;
+        else
+            beg = mid + 1;
+    }
+
+    return -1;
+}
+```
+
+Както забелязваме, на всяка итерация от цикъла размерът на интервала, в който търсим, намалява наполовина и така, докато не стане с размер 1 (когато beg и end се срещнат).
+Съответно ако размера на колекцията ни е n и сме направили x стъпки, то за да намерим x, трябва да решим следното уравнение:
+
+$$
+\frac{n}{2^x} = 1
+$$
+
+От уравнението имаме:
+
+$$
+\frac{n}{2^x} = 1 \implies n = 2^x \implies x = \log_2 n \implies \Theta(\log n)
+$$
+
+Получихме, че алгоритъмът има сложност O(logn) в `worst-case`. 
+
+Нека в `average-case` сме направили k стъпки. На всяка една от стъпките n ще се променя както следва:
+
+- Първа итерация: $n$
+- Втора итерация: $\frac{n}{2}$
+- Трета итерация: $\frac{n}{4}$
+- 
+...
+- k-та итерация: $\frac{n}{2^{k-1}}$
+
+Съответно намираме сложността чрез уравнението:
+
+$$
+\frac{n}{2^k} = t \implies \frac{n}{t} = 2^k \implies k = \log_2 \frac{n}{t} \implies ≈\Theta(\log n)
+$$
+
+`Best-case` ще имаме, когато елементът, който търсим, е точно в средата. Съответно сложността ни тогава е константна (O(1)) - няма да разглеждаме други интервали.
+
+## Стандартни алгоритми за търсене - `std::find`, `std::find_if` и `std::find_if_not`
+В стандартната библиотека имаме алгоритъм, който ни намира даден елемент в колекция. Този алгоритъм се нарича `std::find`. Имплементиран е на базата на линейното търсене, което прави и слоцността му линейна.
+Използва итератори съответно към началото и края на range-a, в който ще търсим елемента, и връща итератор към намерения елемент. Ако не го намери, връща итератор към края на колекцията.
+Ето една възможна имплементация, използваща итератори:
+
+```c++
+template<class RandomIt, class T = typename std::iterator_traits<RandomIt>::value_type>
+constexpr RandomIt find(RandomIt first, RandomIt last, const T& value)
+{
+    for (; first != last; ++first)
+    {
+        if (*first == value)
+            return first;
+    }
+ 
+    return last;
+}
+```
+
+Съответно има негови модификации, които ни позволяват да търсим елемент, който отговаря (или не отговаря) на даден критерий. Това са методите `std::find_if` и `std::find_if_not`. 
+И двата метода приемат предикат, като връщат първия елемент, който отговаря (респективно не отговаря) на него. Ако няма такъв, отново връщат итератор към края. 
+
+Нека видим възможни имплементации:
+
+```c++
+template<class RandomIt, class UnaryPred>
+const RandomIt find_if(RandomIt first, RandomIt last, UnaryPred p)
+{
+    for (; first != last; ++first)
+        if (p(*first))
+            return first;
+ 
+    return last;
+}
+```
+
+```c++
+template<class RandomIt, class UnaryPred>
+const RandomIt find_if_not(RandomIt first, RandomIt last, UnaryPred p)
+{
+    for (; first != last; ++first)
+        if (!p(*first))
+            return first;
+ 
+    return last;
+}
+```
+
+
+## `std::upper_bound` и `std::lower_bound`
+`std::upper_bound` и `std::lower_bound` отново са методи от стандартната библиотека, базирани на алгоритми за търсене. Особеното тук е, че са базирани на двоичното търсене, т.е. задължават колекцията ни да е сортирана предварително, за да ги използваме. 
+Сложността им е съответно O(logn).  
+
+`std::upper_bound` приема итератори към началото и края на range-a, в който ще търси, както и елемент. Връща итератор към първия елемент от колекцията, който е по-голям от подадения.
+Ако няма такъв, връща итератор към края. 
+
+`std::lower_bound` е подобна - приема итератори към началото и края на range-a, в който ще търси, както и елемент. Връща итератор към първия елемент от колекцията, който е по-голям **или равен** на подадения.
+Ако няма такъв, връща итератор към края.
+
+Да разгледаме и примерни имплементации:
+
+```c++
+template <class RandomIt, class T = typename std::iterator_traits<RandomIt>::value_type>
+RandomIt lower_bound(RandomIt beg, RandomIt end, const T& value) {
+    while (beg < end) {
+        RandomIt mid = beg + (end - beg) / 2;
+
+        if (*mid < value) 
+            beg = std::next(mid);
+        else
+            end = mid;
+    }
+    return beg;
+}
+```
+
+```c++
+template <class RandomIt, class T = typename std::iterator_traits<RandomIt>::value_type>
+RandomIt upper_bound(RandomIt beg, RandomIt end, const T& value) {
+    while (beg < end) {
+        RandomIt mid = beg + (end - beg) / 2;
+
+        if (*mid <= value) 
+            beg = std::next(mid);
+        else
+            end = mid;
+    }
+    return beg;
+}
+```
+
+---
+
+## Задачи
+[**Линк към задачите**](https://leetcode.com/problem-list/auzfnnwr/)