# Практикум №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`. 

`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/)