Алгоритмы на языке «разделяй и властвуй». Понятие о классах r и np, np-полных задачах

Алгоритм линейного поиска
Алгоритм линейного поиска — это очень простой алгоритм, который сравнивает каждый элемент массива один за другим с искомым элементом. Сложность алгоритма составляет O(n), что в реальной жизни может быть намного медленнее. Давайте представим, что у Facebook 1 миллиард пользователей, и пользователь хочет получить доступ к своему профилю. В этом случае Facebook проверяет логин пользователя с помощью линейного поиска, а компьютер делает это со скоростью 10 в секунду.⁶даже если бы он проверил логин, ему пришлось бы ждать 1000 секунд (16,6 минут), чтобы получить доступ к профилю этого пользователя. Вот почему нам нужны более эффективные алгоритмы для таких случаев.
Принцип работы алгоритма бинарного поиска
Чтобы понять принцип работы алгоритма бинарного поиска, давайте поиграем с компьютером. Условия игры следующие:
1. Компьютер выбирает произвольное число от 1 до 100. Ваша задача — найти это число, используя как можно меньше догадок.
2. После каждой догадки компьютер сообщает вам, больше или меньше ваша догадка, чем число, которое предполагалось компьютером.
3. Если ваша догадка совпадает с числом, которое угадал компьютер, игра окончена.
Так что бы вы сделали, чтобы брать меньше?
В случае, когда число равно 100, мы можем найти любую догадку не более чем за 7 шагов. Алгоритм бинарного поиска работает по тому же принципу!

Шаги алгоритма

Для корректной работы алгоритма бинарного поискамассив должен быть отсортирован! У нас есть отсортированный массив из n элементов и мы ищем из него x элементов. Мы используем параметры l (слева) и r (справа), чтобы определить предел поиска. Они показывают индексы массива. Переменная mid указывает индекс среднего элемента поля, которое мы ищем
1. Изначально l = 0 и r=n-1 (целочисленный массив)
2. Вычисляется индекс среднего элемента: mid = (l + r)/2;
3. Поисковый номер x сравнивается с индексом среднего элемента
4. Если число совпадает, алгоритм на этом останавливается.
5. Если x больше числа в середине, то перемещаем левый указатель на следующий элемент из середины: l=mid + 1;
6. Если x меньше числа в середине, то перемещаем правый указатель на один элемент до середины: r=mid — 1;
7. Вернитесь к шагу 2.
Поскольку алгоритм бинарного поиска уменьшает n пополам на каждом шаге, скорость работы алгоритма равна O(logn). Для сравнения, алгоритм бинарного поиска может найти 1 миллиард логинов на примере Facebook за 30 (!) шагов. Помимо простого поиска, этот алгоритм можно использовать во многих других местах.