# Алгоритмы поиска

Мы постоянно что-то ищем с помощью компьютера — номера телефонов, свободные номера в гостиницах, товары в интернет-магазинах, квартиры в аренду. За каждым из этих поисков скрываются разные алгоритмы. Среди них — поиск подстроки, поиск по ключевым словам, префиксный поиск. Мы познакомимся с двумя алгоритмами: *методом перебора* и *бинарным поиском*

### Метод перебора

* Он же *линейный (последовательный) поиск* — проверка всех значений в списке с начала и до нужного атрибута.  Выделяют два алгоритма перебора — **поиск по списку** и **поиск по ключу**

*Поиск по списку:* если нам нужно найти слово в списке слов — мы последовательно будем проверять все слова, пока не найдём нужное

*Поиск по ключу*: 

* Допустим у нас есть список городов с датами основания. Мы знаем год основания города и хотим найти его название. Так, мы знаем один атрибут города — год основания, а хотим найти другой атрибут — название города. Известный нам атрибут называется **ключом**, по которому мы проводим поиск

<figure><img src="https://1822329473-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2Fht6R7IOuWvAQ9gEYvkFW%2Fuploads%2Fw9AWmopMoF4WN64BrEry%2Fimage.png?alt=media&#x26;token=4dc9f8cf-e0d9-4497-985c-ea7608991b8f" alt=""><figcaption><p>Список городов с датами основания</p></figcaption></figure>

* *Интерактив:* попробуйте поразмышлять — какое действие сильно облегчило бы подобный поиск по ключу

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

{% code overflow="wrap" %}

```python
some_cities = ["Ереван", "Киев", "Минск", "Рига", "Вильнюс", "Астана", "Москва", "Баку", "Душанбе", "Хельсинки", "Ашхабад", "Ташкент"]

def is_city(some_cities, candidate):
    for i in range(len(some_cities)):
        if some_cities[i] == candidate:
            return True
    return False
```

{% endcode %}

* Представим, что по такому методу работает проверка логина и пароля в Facebook. Массив с логинами-паролями всех пользователей содержит около трех миллиардов элементов и даже на самых быстрых серверах этот процесс занял бы **несколько минут**

#### Как ускорить алгоритм перебора

Самый простой способ — упорядочить данные, т.е. отсортировать их. Представьте, если бы в телефонном справочнике имена и фамилии не были бы отсортированы, сколько бы занял поиск номера. А если они отсортированы по алфавиту, мы сразу можем "отсечь" часть списка, в котором искомой фамилии точно нет.

### Бинарный поиск

Это метод поиска, при котором алгоритм ищет элементы в ограниченной области поиска, причем с каждым шагом область поиска делится на две части.

*Механизм работы:*

* Бинарный поиск начинается со среднего элемента и на первом шаге идёт по всему массиву
* На каждом шаге область поиска делится пополам, при этом границы поиска задаются первым и последним элементом
* Алгоритм завершается, когда область поиска сужается до одного элемента

Необходимое условие для применения бинарного поиска — массив должен быть *отсортирован.*&#x20;

Отсортируем массив городов по алфавиту:

```python
some_cities = ['Астана',
               'Ашхабад',
               'Баку',
               'Вильнюс',
               'Душанбе',
               'Ереван',
               'Киев',
               'Минск',
               'Москва',
               'Рига',
               'Ташкент',
               'Хельсинки']
```

* Изначально *область поиска* — весь массив.&#x20;
* Делим его пополам, в середине элемент `"Киев"`, сравниваем его с искомым — таким образом сужаем *область поиска* до половины массива. И далее делим пополам уже оставшуюся область поиска.

*Практика:*

* Составьте псевдокод для программы поиска города в списке городов из примера выше.

Посмотрим на реализацию в коде:

{% code overflow="wrap" %}

```python
some_cities = ['Астана', 'Ашхабад', 'Баку', 'Вильнюс', 'Душанбе', 'Ереван', 'Киев', 'Минск', 'Москва', 'Рига', 'Ташкент', 'Хельсинки']

def is_some_city(some_cities, candidate):
    # индекс первого элемента области поиска
    first = 0
    # индекс последнего элемента области поиска
    last = len(some_cities) - 1

    while (first <= last):
        # индекс среднего элемента области поиска
        middle = (first + last) // 2

        if candidate == some_cities[middle]:
            # если нашли слово-кандидат, поиск завершается удачно
            return True

        if candidate < some_cities[middle]:
            # если кандидат меньше, отбрасываем правую половину
            last = middle - 1
        else:
            # если кандидат больше, отбрасываем левую половину
            first = middle + 1

    return False
```

{% endcode %}

#### Недостатки бинарного поиска

Мы рассмотрели линейный и бинарный поиск на примере списка городов. Обратим внимание на ограничения использования бинарного поиска:

* Бинарный поиск **сложнее в реализации**. Если у нас массив более 100 элементов имеет смысл воспользоваться бинарным поиском, если массив небольшой — достаточно метода перебора, он будет работать со сравнимой скоростью или даже быстрее
* Массив для бинарного поиска **должен быть упорядоченным.** Это не проблема, если массив фиксированный, т.е. данные не меняются по ходу работы программы, а подготавливаются один раз. Но если данные нужно добавлять — придётся писать дополнительный сложный код.
* Существуют данные, которые невозможно упорядочить (например, цвета или пары чисел — координаты: широта и долгота)

#### Преимущества бинарного поиска

Бинарный поиск быстрее линейного, но насколько? Как это измерить?

* Мы можем измерить время работы программ. Но это время сильно зависит от конкретной машины и условий (фоновые задачи и т.п.), а поэтому не является объективным.
* Оценим скорость теоретически — быстрее тот алгоритм, в котором совершается меньше операций. В обоих алгоритмах операции проходят в цикле и для объективности будем считать среднее количество циклов

<figure><img src="https://1822329473-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2Fht6R7IOuWvAQ9gEYvkFW%2Fuploads%2FgIR9sHzdcXJvfC1Uwdn4%2Fimage.png?alt=media&#x26;token=ab0d859e-4809-4510-a41c-4371286e395c" alt=""><figcaption><p>Сравнение средней скорости алгоритмов поиска</p></figcaption></figure>

### Заключение

* Мы рассмотрели два алгоритма: метод перебора и бинарный поиск
* У метода перебора есть два варианта:
  * Простой перебор, чтобы проверить, есть ли элемент в списке
  * Поиск по ключу, если нужно найти элемент по одному атрибуту
* Бинарный поиск позволяет искать элементы в упорядоченном списке. На каждом шаге алгоритма область поиска делится на две части.
* Бинарный поиск гораздо быстрее обычного поиска, но при этом сложнее в реализации

### Практика

* **Поиск максимального элемента:** Дан массив чисел. Найдите максимальный элемент в этом массиве, используя линейный поиск.
* **Поиск первого вхождения элемента:** Дан массив строк и ключевое слово. Найдите индекс первого вхождения ключевого слова в массиве, используя линейный поиск.
* **Поиск элемента в отсортированном массиве:** Дан отсортированный массив чисел и элемент этого массива. Найдите индекс элемента, используя бинарный поиск.

### Вычислительная сложность

Как понять, насколько быстро работает алгоритм?

* Попробуем рассчитать время выполнения алгоритма. Допустим, время выполнения одной операции составляет 1 мс. Одной операцией для поиска является одно прохождение по массиву. Для линейного поиска в массиве из 100 элементов время составит 100 мс (в худшем случае).  Для бинарного поиска — 7 мс. *Посчитайте, сколько времени понадобится для линейного и бинарного поиска в массиве из 1000 элементов*
* Мы видим, что с увеличением размера массива время выполнения линейного и бинарного поиска увеличивается, но с существенно разной скоростью

<figure><img src="https://1822329473-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2Fht6R7IOuWvAQ9gEYvkFW%2Fuploads%2FHXQMzHtZs6SCLxl30zKy%2Fimage.png?alt=media&#x26;token=04802060-c557-48a3-830b-3a89b7b806e7" alt=""><figcaption></figcaption></figure>

* Таким образом, для линейного поиска по массиву длиной N элементов нужно в худшем случае нужно произвести **N** операций. Для бинарного поиска — **log N** операций — степень числа 2, в которую нужно её возвести, чтобы получить N
* Для того, чтобы понимать, насколько быстро или медленно работают алгоритмы используют нотацию O (**"О-большое"**). С её использованием формулировка будет выглядеть так — *скорость работы алгоритма линейного поиска составляет **O(n)**, а скорость работы бинарного поиска составляет **O(log n)***
* О-большое позволяет сравнить *количество операций* — именно так принято сравнивать скорость работы алгоритмов. Чаще всего используют *худший случай*, т.е. максимальное возможное количество операций для алгоритма, но иногда учитывают и *среднее время* выполнения
* Типичные примеры О-большого:
  * **O(log n)**, или логарифмическое время. *Пример:* бинарный поиск.
  * **O(n)**, или линейное время. *Пример:* простой поиск.
  * **O(n\*log n)**. *Пример:* эффективные алгоритмы сортировки
  * **O(n2)**. *Пример:* медленные алгоритмы сортировки
  * **O(n!)**. *Пример:* очень медленные алгоритмы (задача о коммивояжёре)

***Практика:***

Приведите время выполнения "О-большое" для каждого из следующих сценариев:

* Известная фамилия, нужно найти номер в телефонной книге
* Известен номер, нужно найти фамилию в телефонной книге