Линейный и двоичный поиски в упорядоченном массиве

Линейный поиск

Мы считаем, что вы уже знаете линейный поиск, а именно умеете решать задачи такого типа:

• Проверить, есть ли в массиве число X
• Найти максимум в массиве
• Найти сумму чисел в массиве
• Найти первое четное число в массиве

Все такие задачи решаются с помощью одного прохода по массиву с помощью цикла for. Все такие алгоритмы работают за \(O(n)\). И даже можно понять, что быстрее, чем \(O(n)\) решить ни одну из этих задач не получится.

Задание

Убедитесь, что вы умеете решать эти задачи. Докажите, что быстрее, чем O(n) их решить в худшем случае нельзя.

Что такое линейный поиск?

Линейный поиск — это алгоритм оптимизации для одномерной или многомерной оптимизации. Он требует начальной позиции в пространстве поиска, а также указания направления поиска. Затем он из начальной выбирает следующую позицию в пространстве поиска, которая приведёт к значению лучше или же к наилучшему значению целевой функции.

Направление имеет знак (плюс или минус) вдоль линии и максимальную протяжённость поиска, поэтому его лучше рассматривать как область поиска кандидатов, оно должно быть достаточно большим, чтобы охватить оптимумы или точку лучше начальной.

Линейный поиск автоматически выберет коэффициент масштаба, который называется альфа, для размера шага (направления) исходя из текущей, минимизирующей целевую функцию позиции. Чтобы найти оптимальную точку в выбранном направлении и выбрать соответствующую альфа, используется другой алгоритм одномерной оптимизации

Один из подходов заключается в применении линейного поиска, выбирающего коэффициент шага, который минимизирует одномерную функцию […]. Мы можем применить метод одномерной оптимизации по нашему выбору.

— Алгоритмы оптимизации, 2019. — С. 54.

Альфа — коэффициент масштаба для направления, поэтому при поиске учитываются только значения в диапазоне от 0,0 до 1,0. Один шаг линейного поиска решает задачу минимизации, которая минимизирует целевую функцию для текущей позиции в сумме с масштабируемым направлением, то есть:

• Минимизирует objective(position + alpha * direction).

Таким образом, линейный поиск работает в одном измерении за один раз и возвращает расстояние перемещения в выбранном направлении.

Каждая итерация метода линейного поиска вычисляет направление поиска pk, а затем решает, как далеко двигаться в этом направлении.

— Численная оптимизация, 2006. — С. 30. 

Чтобы перенести пространство поиска к решению, линейный поиск может быть вызван повторно и может завершиться неудачей, если выбранное направление не содержит точки с меньшим значением целевой функции, например когда алгоритм направлен искать по склону вверх.

Решение приблизительно или неточно и в зависимости от формы пространства поиска может не оказаться общим решением. Условия, при которых этот алгоритм подходит, называются условиями Вольфе. Теперь, когда мы знакомы с линейным поиском, давайте посмотрим, как выполнять его на Python.

Видео

Пространственная сложность

Одна единица пространства требуется для хранения искомого элемента. Следовательно, пространственная сложность равна O(1).

Рекурсивный двоичный поиск хранит вызов метода в стеке. В худшем случае пространственная сложность потребует O(log (N)).

Алгоритм

Есть список из n элементов и ключевого значения для поиска. Ниже представлен алгоритм линейного поиска.

Временная сложность

Для получения позиции искомого элемента перебирается набор из N элементов. В худшем сценарии для этого алгоритма искомый элемент оказывается последним в массиве.

В этом случае потребуется N итераций для нахождения элемента.

Следовательно, временная сложность линейного поиска равна O(N).

 Как создать линейный поиск

Давайте посмотрим как работает линейный поиск на практике.В примере ниже мы создали массив на 20 элементов и заполнили его ячейки случайными числами с помощью функции rand.

В строке 26 мы предлагаем пользователю с клавиатуры ввести ключ, а дальше мы проверим массив на наличие этого ключа. Если ключ совпал с какой-то ячейкой в массиве, то мы выведем индекс этой ячейки. Это типичный пример чтобы понять как работает алгоритм.

C++

#include <iostream> #include <cstdlib> #include <ctime> using namespace std; int main() { setlocale(LC_ALL, «rus»); int ans[20]; // создали массив для записи всех индексов int h = 0; int arr[20]; // создали массив на 20 элементов int key; // создали переменную в которой будет находиться ключ srand ( time(NULL) ); for (int i = 0; i < 20; i++) { arr[i] = 1 + rand() % 20; // заполняем случайными числами ячейки cout << arr[i] << » «; // выводим все ячейки массива if (i == 9) { cout << endl; } } cout << endl << endl << «Введите ключ : «; cin >> key; // считываем ключ for (int i = 0; i < 20; i++) { if (arr[i] == key) { // проверяем равен ли arr[i] ключу ans[h++] = i; } } if (h != 0) { // проверяем были ли совпадения for (int i = 0; i < h; i++) { cout << «Ключ » << key << » находится в ячейке » << ans[i] << endl; //выводим все индексы } } else { cout << «Мы не нашли ключ » << key << » в массиве»; } system(«pause»); return 0; }

123456789101112131415161718192021222324252627282930313233343536373839404142434445 #include <iostream> #include <cstdlib> #include <ctime> using namespace std ; int main ( ) { setlocale ( LC_ALL , «rus» ) ; int ans [ 20 ] ; // создали массив для записи всех индексов int h = ; int arr [ 20 ] ; // создали массив на 20 элементов int key ; // создали переменную в которой будет находиться ключ srand ( time ( NULL ) ) ; for ( int i = ; i < 20 ; i ++ ) { arr [ i ] = 1 + rand ( ) % 20 ; // заполняем случайными числами ячейки cout << arr [ i ] << » » ; // выводим все ячейки массива if ( i == 9 ) { cout << endl ; } } cout << endl << endl << «Введите ключ : » ; cin >> key ; // считываем ключ for ( int i = ; i < 20 ; i ++ ) { if ( arr [ i ] == key ) { // проверяем равен ли arr[i] ключу ans [ h ++ ] = i ; } } if ( h != ) { // проверяем были ли совпадения for ( int i = ; i < h ; i ++ ) { cout << «Ключ » << key << » находится в ячейке » << ans [ i ] << endl ; //выводим все индексы } } else { cout << «Мы не нашли ключ » << key << » в массиве» ; } system ( «pause» ) ; return ; }

Линейный поиск находится в строках 28 — 32.

Давайте разберем этот пример:

1. В строке 9 — 10: мы создали массив ans и переменную h (равную нулю).

В массиве ans будут храниться все индексы.

1. В строке 29: мы применили оператор ветвления if.
   • Если результат условия положительный, то в ячейку ans[h] присваиваем значение i, а переменную h увеличиваем на один.

1. В строке 34: проверяем:
   • Если результат условия положителен, то выводим h первых элементов массива ans;
   • Если же результат условия отрицателен, то выводим «Мы не нашли ключ key в массиве»

Давайте выполним этот код:

line_search.cpp

2 8 15 1 10 5 19 19 3 5 6 6 2 8 2 12 16 3 8 17 Введите ключ : 8 Ключ 8 находится в ячейке 1 Ключ 8 находится в ячейке 13 Ключ 8 находится в ячейке 18 Process returned 0 (0x0) execution time : 0.020 s Press any key to continue.

А если такого ключа нет в массиве :

line_search.cpp

19 1 14 9 2 12 6 14 8 2 11 16 3 4 2 16 19 14 7 15 Введите ключ : 5 Мы не нашли ключ 5 в массиве Process returned 0 (0x0) execution time : 0.020 s Press any key to continue.

Анализ

Для списка из n элементов лучшим случаем будет тот, при котором искомое значение равно первому элементу списка и требуется только одно сравнение. Худший случай будет тогда, когда значения в списке нет (или оно находится в самом конце списка), в случае чего необходимо n сравнений.

Если искомое значение входит в список k раз и все вхождения равновероятны, то ожидаемое число сравнений

Например, если искомое значение встречается в списке один раз, и все вхождения равновероятны, то среднее число сравнений равно . Однако, если известно, что оно встречается один раз, то достаточно n — 1 сравнений и среднее число сравнений будет равняться

(для n = 2 это число равняется 1, что соответствует одной конструкции if-then-else).

В любом случае, вычислительная сложность алгоритма O(n).

Поиск максимума выпуклой функции: тернарный поиск, бинарный поиск

Так мы только что научились находить корень непрерывной функции, у которой мы знаем значение меньше и больше 0. Но можно ли найти с помощью бинарного поиска локальный максимум функции? Можно!

Как известно, локальный максимум функции \(f\) — это просто такое \(x_0\), что для всех близких к нему \(x\) значения \(f(x) < f(x_0)\). Для непрерывных функций выполняется более крутая вещь: слева от максимума функция возрастает, а справа от максимума функция убывает. Так это как раз отличное условие для нашего вещественного бинарного поиска!

Если вы знаете \(x_1\) такое, что в его окрестности f(x) возрастает, и \(x_2\) такое, что в его окрестности f(x) убывает, то можно запустить между ними бинпоиск и найти точку \(x_0\) такую, что слева от нее возрастает значение функции, а справа — убывает. Это и есть локальный максимум.

А если функция выпуклая, то она вообще выглядит красиво: сначала возрастает, потом максимум, потом убывает.

Проблема только в одном: как по точке понять, в ее окрестности значение функции убывает или возрастает? Достаточно тыкнуть две точки очень-очень рядом с ней и сравнить их значения!

Задание

Придумайте, как с помощью вещественного бинпоиска найти * максимум функции \(x — e^x\) (она выпуклая, и максимум ровно один) * какой-нибудь локальный максимум функции \(31x+x^3-x^4\)

Тернарный поиск

Другой способ искать максимум — это тернарный поиск. Пусть известно, что максимум находится между left и right. Поделим отрезок на три равные части: * middle_left = (2 * left + right) / 3 * middle_right = (left + 2 * right) / 3

Тогда если f(middle_left) < f(middle_right), то можно спокойно заменить left на middle_left (максимум точно не левее middle_left), а если f(middle_left) > f(middle_right), то можно спокойно заменить right на middle_right. Он будет работать не за двоичный логарифм, а за логарифм по основанию полтора, что больше (но асимптотически то же самое, так как отличается в константу раз).

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

Бинарный поиск по неотсортированному массиву

Заметьте, что в первоначальной задаче условие на то, что сначала идут нули, а потом идут единицы несущественно. Главное, чтобы мы знали индекс, который показывает на 0, и индекс, который показывает на 1. После этого бинарным поиском мы таким же способом найдем пару соседних нуля и единицы в массиве.

Поэтому бинарный поиск работает и не для возрастающих массивов / функций, если наша задача состоит именно в поиске двух соседних индексов, в которых условие выполняется и не выполняется.

Например, если мы знаем, что \(f(x_0) < 0\) и \(f(x_1) > 0\), и функция непрерывная, то бинарным поиском можно найти ноль этой функции между \(x_0\) и \(x_1\), даже если функция не монотонная!

Или, например, если нужно в массиве найти соседние четное и нечетное числа, и известно положение какого-то четного числа и какого-то нечетного числа, то это тоже можно легко сделать с помощью бинарного поиска.

Полезно иметь это в виду, это применяется в нескольких задачах контестов.

Теги