23. Способы поиска в массивах.
1) Линейный поиск (осуществляется в неотсортированных массивах).
Задача. Найти в линейном массиве элемент, равный k и вывести его номер. Если этого элемента в массиве нет, то вывести несуществующий индекс.
d: array [1..n] of char;
until (i=n) or (a[i]=k);
then write(‘не найдено’,’0′)
2) Дихотомический поиск (метод половинного деления).
Производится деление пополам в области поиска отсортированного массива. Определяется, в какой половине располагается искомый элемент. Сужаются границы области поиска до предыдущей половины.
3) Поиск с барьером.
Идея поиска с барьером состоит в том, чтобы не проверять каждый раз в цикле условие, связанное с границами массива. Это можно обеспечить, установив в массив так называемый барьер: любой элемент, который удовлетворяет условию поиска. Тем самым будет ограничено изменение индекса.
Выход из цикла, в котором теперь остается только условие поиска, может произойти либо на найденном элементе, либо на барьере. Таким образом, после выхода из цикла проверяется, не барьер ли мы нашли? Вычислительная сложность поиска с барьером меньше, чем у линейного поиска, но также является величиной того же порядка, что и N — количество элементов массива. Существует два способа установки барьера: дополнительным элементом или вместо крайнего элемента массива.
ПРИМЕР: Поиск с барьером
var A:array[1..101] of integer;
for i:=1 to N do read(A[i]);
if i<=N then write(‘первое вхождение числа ‘,X,’ в массив A на ‘,i,’ месте’)
else write(‘не нашли’);
var A:array[1..100] of integer;
for i:=1 to N do read(A[i]);
if (i<N) or (y=X) then
write(‘первое вхождение числа ‘,X,’ в массив A на ‘,i,’ месте’)
else write(‘не нашли’);
Поиск максимального или минимального элемента массива.
Задачу поиска минимального элемента массива рассмотрим на примере массива целых чисел. Алгоритм поиска минимального (максимального) элемента массива довольно очевиден: сначала делается предположение, что первый элемент массива является минимальным (максимальным), затем остальные элементы массива последовательно сравниваются с этим элементом. Если во время очередной проверки обнаруживается, что проверяемый элемент меньше (больше) принятого за минимальный (максимальный), то этот элемент становится минимальным (максимальным) и продолжается проверка оставшихся элементов.
Поиск в массиве заданного элемента
При решении многих задач возникает необходимость определить, содержит ли массив определенную информацию или нет. Задачи такого типа называются поиском в массиве. Для организации поиска в массиве могут быть использованы различные алгоритмы. Наиболее простой — это алгоритм простого перебора. Поиск осуществляется последовательным сравнением элементов массива с образцом до тех пор, пока не будет найден элемент, равный образцу, или не будут проверены все элементы. Алгоритм простого перебора применяется, если элементы массива не упорядочены.
Метод бинарного поиска
На практике довольно часто производится поиск в массиве, элементы которого упорядочены по некоторому критерию (такие массивы называются упорядоченными). Например, массив фамилий, как правило, упорядочен по алфавиту. Если массив упорядочен, то применяют метод бинарного поиска.
Метод (алгоритм) бинарного поиска реализуется следующим образом:
1. Сначала образец сравнивается со средним (по номеру) элементом массива.
Если образец равен среднему элементу, то задача решена.
Если образец больше среднего элемента, то это значит, что искомый элемент расположен ниже среднего элемента (между элементами с номерами sred+1 и niz), и за новое значение verb принимается sred+i, а значение niz не меняется.
Если образец меньше среднего элемента, то это значит, что искомый элемент расположен выше среднего элемента (между элементами с номерами verh и sred-1), и за новое значение niz принимается sred-1, а значение verh не меняется.
После того как определена часть массива, в которой может находится искомый элемент, по формуле (niz-verh) /2+verh вычисляется новое значение sred и поиск продолжается.
Алгоритм бинарного поиска заканчивает свою работу, если искомый элемент найден или если перед выполнением очередного цикла поиска обнаруживается, что значение verh больше, чем niz.
Алгоритмы поиска
Алгоритмы поиска значения в массиве данных могут не иметь никаких особых требований к входным данным, и такие алгоритмы мы сравним между собой. Если же о входных данных заранее кое-что известно (например, что они упорядочены по алфавиту), то для таких данных могут быть применены другие, более быстродействующие алгоритмы.
Итак, по порядку от самого простого для понимания, с иллюстрацией кодом на JavaScript. Для всех алгоритмов A — массив входных данных, n — его длина, x — значение, которое хотим найти. Нас будет интересовать индекс элемента массива, имеющего искомое значение. Если результат не найден, то возвращается специальное значение «NOT FOUND».
Линейный поиск
Самый простой метод. Перебираем последовательно все элементы массива и каждый сравниваем с искомым значением. Если они равны, то запоминаем индекс. Слабость алгоритма в том, что нам приходится перебирать все элементы, вне зависимости от того, где находится искомый элемент.
Реализация на JavaScript:
Так как алгоритм всегда проходит n итераций, соответственно, можно сказать, что его быстродействие θ(n). (смотри статью про асимптотические нотации).
Усовершенстованный линейный поиск
На самом деле первый алгоритм был несколько надуманным, потому что нет смысла перебирать все оставшиеся значения в массиве, если мы уже нашли искомое. Вот эта идея тут и реализуется.
Поскольку здесь мы не всегда пробегаем по всем значениям, то быстродействие алгоритма (по-научному -его асимптотическая сложность) очень разнится для самого плохого и самого хорошего случаев — от θ(1) до θ(n). Можно сказать, что алгоритм имеет O(n).
Линейный поиск со сторожем (sentinel)
Здесь идея в том, что мы сохраняем последний элемент массива во временной переменной, чтобы на его место записать искомое значение. Это нужно, чтобы вместо цикла for использовать while без риска получить зацикливание, если в массиве не окажется искомой величины. В целом, все эти пляски подразумевают сокращение сравнений в каждой итерации с двух до одного. В описанных выше алгоритмах нам нужно проверить i<n, а затем A[i]=x. В данном же алгоритме проверка одна. Дает ли это выигрыш — зависит от конкретного языка программирования и процессора.
Цена одной итерации здесь может быть ниже, чем у улучшенного линейного поиска, но в асимтотической нотации всё то же самое: от θ(1) до θ(n) и O(n).
Рекурсивный линейный поиск
Тут всё то же самое, только с использованием рекурсии. Просто для иллюстрации.
Двоичный поиск
Этот алгоритм подразумевает, что входной массив уже отсортирован (например, по алфавиту). Только в этом случае можно применять двоичный поиск. Здесь в каждой итерации массив делится на две части, и мы сравниваем срединное значение с искомым. Соответственно, принимаем решение, что может находиться только в левой или только в правой части массива (оказалось больше или меньше границы раздела). Отсекаем ту часть, в которой искомого значения быть не может, таким образом, сразу же уменьшая количество итераций в два раза. Так делаем на каждой следующей итерации, пока «граничное» значение не окажется тем, что мы ищем.
Реализация на JavaScript:
Быстродействие (асимптотическая сложность) этого алгоритма O(lb(n)). Здесь lb(n) — это логарифм по основанию 2 (двоичный логарифм).
Алгоритмы поиска в олимпиадных задачах
Данную тему следует рассматривать в двух аспектах. Во-первых, при решении различных олимпиадных задач алгоритмы поиска приходится использовать в качестве технических элементов при реализации собственно алгоритма решения той или иной задачи. Во-вторых, задача сама по себе может требовать построения оптимального в смысле определенных требований алгоритма поиска. Подход в каждом из двух упомянутых случаев должен быть различным.
Для полноценного понимания темы рекомендую просмотреть следующие статьи:
А для продолжения изучения — выбрать себе какую-нибудь книгу по алгоритмам.
Алгоритмы поиска в неупорядоченных одномерных массивах
Рассмотрим сначала нюансы реализации “технических” задач поиска, которые встречаются в различных алгоритмах. Начнем с, казалось бы, тривиальной задачи поиска элемента в неупорядоченном массиве. Во всех примерах, относящихся к поиску в одномерном массиве будем использовать следующую переменную a :
a:array[0..N] of <скалярный тип>;
при этом собственно элементы массива, которые мы будем рассматривать, пронумерованы от 1 до N , а нулевой элемент будем использовать как вспомогательный в случае необходимости. Конкретный же тип элемента в большинстве описываемых алгоритмов не важен, он может быть как любым числовым, так и символьным или даже строковым. Алгоритм поиска в массиве элемента, значение которого равно K , может выглядеть так:
При отсутствии в массиве элемента с искомым значением K печатается значение нулевого индекса. Оказывается, что и такую достаточно простую программу можно упростить, заодно продемонстрировав так называемый “барьерный” метод, который часто применяется в программировании в том числе и олимпиадных задач. В данном случае он заключается в том, что мы можем занести в дополнительный элемент массива (например, нулевой) искомое значение K, избавившись тем самым в условии окончания цикла от проверки на выход за границу массива:
Эта программа не просто проще и эффективней. В ней практически невозможно сделать ошибку.
Другой полезный прием можно показать на задаче поиска максимального и минимального значения в массиве. Состоит он в том, что при любом поиске в массиве искать следует не значение искомого элемента, максимума, минимума и т.п., а его индекс. Тогда решая одну задачу, мы по сути дела решаем сразу две: определяем не только наличие искомого элемента, значение максимума или минимума, но и их местоположение в массиве. Программа при этом не только не усложняется, но зачастую становится даже короче:
Заметим, что использование в качестве начальных значений для минимума и максимума не значение первого элемента массива, а максимальное и минимальное значение в типе элементов, может привести к ошибке. Так, следующая программа не находит значение максимума для убывающего массива целых чисел (. ):
Казалось бы на этом рассмотрение алгоритмов поиска в неупорядоченном массиве можно завершить. Однако именно с одновременного поиска минимума и максимума можно начать класс алгоритмов поиска, более эффективных, чем приведенные выше стандартные алгоритмы. Причем именно при решении олимпиадных задач их знание может пригодиться в первую очередь. Итак, в приведенном выше алгоритме поиска максимального и минимального элемента в массиве в худшем случае выполняется 2N – 2 сравнений. Покажем, что ту же задачу можно решить за 3*round(N/2) – 2 сравнения. Пусть у нас имеется четное число элементов. Разобьем их на пары и в каждой из N/2 пар за одно сравнение определим, какой элемент больше, а какой меньше. Тогда максимум можно искать уже любым способом только из наибольших элементов в парах, а минимум — среди наименьших. Общее число сравнений при этом равно N/2 + 2(N/2 – 1) = 3N/2 – 2 . Для нечетного числа элементов — элемент, не попавший ни в одну из пар, должен участвовать как в поиске максимума, так и минимума.
Обозначение round(A)соответствует для неотрицательных чисел округлению до ближайшего целого числа, большего или равного выражению в указанных скобках, в отличие от целой части, где округление производится до ближайшего целого, меньшего или равного рассматриваемому выражению.
Еще большей эффективности можно добиться при одновременном поиске максимального и второго по величине числа. Для этого организуем поиск максимума по схеме “теннисного турнира”, а именно: разобьем элементы на пары и определим в каждой из пар больший элемент, затем разобьем на пары уже эти элементы и т.д. В “финале” и будет определен максимум. Количество сравнений в таком алгоритме, как и в традиционной схеме, равно N – 1 . Однако, максимальный элемент участвовал при этом в round(log2(N)) сравнениях, причем одно из них проходило обязательно со вторым по величине элементом. Таким образом, теперь для поиска этого элемента потребуется всего round(log2(N)) – 1 сравнение. Попробуйте самостоятельно построить эффективный алгоритм для поиска уже первых трех по величите элементов.
В данном контексте можно поставить также задачу поиска i-го по счету элемента, называемого i-ой порядковой статистикой. Кроме максимума и минимума, специфической порядковой статистикой является медиана — элемент с номером (N + 1)/2 для нечетных N и два соседних элемента для четных. Конечно, задачу поиска любой порядковой статистики можно решить, предварительно отсортировав массив. Но, как будет показано ниже, оптимальные по количеству сравнений универсальные (то есть пригодные для произвольных массивов) алгоритмы сортировки выполняют порядка Nlog2N сравнений. А задачу поиска i-ой порядковой статистики можно решить, производя O(N) сравнений. Алгоритм, который гарантирует эту оценку достаточно сложен, он подробно изложен в [1, 2, 3]. Мы же приведем схему алгоритма, который в худшем случае не является линейным, однако на практике работает существенно быстрее, следовательно именно его и нужно использовать в практике реального программирования, в том числе и олимпиадных задач:
Оптимальную реализацию пункта 3 можно заимствовать из алгоритма так называемой быстрой сортировки (смотри по ссылкам, приведенным в начале статьи).
Наконец, рассмотрим задачу поиска в последовательности из N чисел, хранения которой не требуется вообще, следовательно ее длина может быть очень велика. Пусть известно, что в этой последовательности встречаются по одному разу все числа от 0 до N, кроме одного. Это пропущенное число и требуется найти. Вот возможное решение такой задачи:
Данную программу легко переписать так, чтобы она работала и для значений N, превосходящих максимальное представимое целое число. Для этого следует использовать переменные типа extended , а цикл for заменить на while . Используя аналогичный прием попробуйте решить следующую задачу. Пусть N — количество чисел, нечетно и известно, что среди вводимых чисел каждое имеет ровно одно, равное себе, а одно число — нет. Найдите это число. (Указание. В данном случае можно воспользоваться свойством логической функции “исключающее или”, обозначаемой в Паскале как xor : a xor b xor b = a ).
Поиск в упорядоченных массивах
Под упорядоченными в дальнейшем будут пониматься неубывающие массивы, если не оговорено иное. То есть, a[1] <= a[2] <= … <= a[N] .
Сначала приведем пример реализации широко известного алгоритма двоичного (бинарного) поиска элемента, равного K, в уже упорядоченном массиве. Оказывается, досрочный выход из цикла в случае нахождения элемента выигрыша по скорости практически не дает, а лишние проверки делают программу более громоздкой. Поэтому рекомендуется производить поиск, пока диапазон рассматриваемых элементов состоит более, чем из одного элемента.
Известно, что алгоритм бинарного поиска, аналогичный приведенному выше, но заканчивающий свою работу в случае досрочного обнаружения элемента, за Q сравнений определил, что искомым является элемент с номером I . Какова могла быть при этом размерность массива (указать все допустимые диапазоны значений N ). Несмотря на кажущуюся сложность, при заданных в условии ограничениях задача решалась путем простого перебора различных значений N и обращения с каждым из этих значений к функции бинарного поиска. Конструктивный же подход к решению задачи намного сложнее. Однако и в случае подбора можно использовать немало интересных фактов. Например, длина каждого из диапазонов возможных значений N , является степенью двойки, а каждый следующий диапазон не меньше предыдущего. Это позволяет значительно сократить количество рассматриваемых значений N . Кроме того, максимальное допустимое значение для N легко найти аналитически.
Рассмотрим теперь задачу поиска в упорядоченном массиве наибольшего «равнинного» участка. То есть, требуется найти такое число p, что в массиве имеется последовательность из p равных элементов и нет последовательности из p + 1 равных по значению элементов. Оказывается, существует алгоритм решения этой задачи, количество операций в котором может оказаться существенно меньше, чем N . Так, если мы уже нашли последовательность из p1 равных между собой чисел, то другую последовательность имеет смысл теперь рассматривать только если ее длина не менее p1 + 1 . Поэтому, если a[i] — первый элемент предполагаемой новой подпоследовательности, то сравнивать его надо сразу с элементом a[i+p] , где p — максимальная величина для уже рассмотренных подпоследовательностей из равных элементов. Приведем фрагмент программы, решающий данную задачу. В качестве результата мы получаем длину максимальной подпоследовательности p, номер элемента, с которого эта подпоследовательность начинается, k и значение элементов в найденной подпоследовательности:
Пусть имеются три упорядоченных по алфавиту списка из фамилий людей, получающий пособие по безработице в трех различных местах. Длина каждого из списков может быть как угодно большой (каждый из списков можно хранить в отдельном файле). Известно, что по крайней мере одно лицо фигурирует во всех трех списках. Требуется написать программу поиска такого лица, порядок количества операций в которой не будет больше, чем сумма длин всех трех списков. Приведем фрагмент программы, работающий с тремя файлами, обращение к элементам которых (они могут быть любого типа, в том числе и string , к элементам которого в Паскале применимы операции сравнения, чтения и записи) из программы происходит с помощью файловых переменных x, y, z типа text :
Покажите, что для поставленной задачи чтение из файла всегда будет производиться корректно и на каждом шаге цикла значение одной из трех переменных p, q, r будет изменено. Кроме того докажите, что с помощью этой программы всегда будет найден именно минимальный из элементов, присутствующих во всех трех файлах.
Наконец, рассмотрим задачу поиска элемента, значение которого равно K, в двухмерном массиве, упорядоченном по строкам и столбцам:
Данная задача решается за M + N действий, а не за M*N , как в произвольном массиве. Поиск следует начинать с элемента a[N,1] . Этот элемент самый маленький в своей строке и самый большой в своем столбце (в математике подобные элементы называют “седловыми точками”). Поэтому, если он окажется меньше, чем K, то из рассмотрения первый столбец можно исключить, а если больше — из рассмотрения исключается последняя строка и т. д. Вот возможная реализация этого алгоритма:
Программа могла бы быть еще короче и эффективней, если бы в ней использовался упоминавшийся выше барьерный метод. В данном случае для организации барьера требуется дополнить массив нулевой строкой и m+1-м столбцом. Во все созданные барьерные элементы следует поместить значение K. Тогда условие в цикле можно сократить до следующего: a[i,j]<>K .
Алгоритмы поиска и задачи на взвешивания
Появление подобных задач, например задачи определения фальшивой монеты, в контексте рассмотрения алгоритмов поиска не случайно. Во-первых, поиск и в этом случае осуществляется путем операций сравнения, правда, уже не только одиночных элементов, но и групп элементов между собой. Во-вторых, как будет показано ниже, в отличие от олимпиад по математике для младших школьников, задачи на взвешивания вполне можно решать конструктивно.
В качестве примера рассмотрим задачу, предлагавшуюся на теоретическом туре одной из региональных олимпиад по информатике. Пусть у нас имеется 12 монет, одна из которых фальшивая, по весу отличающаяся от остальных монет, причем неизвестно, легче она или тяжелее. Требуется за три взвешивания определить номер фальшивой монеты (попробуйте решить эту задачу самостоятельно и вы убедитесь, что это совсем не просто, а порой вообще кажется невозможным). Введем следующие обозначения. Знаком “+” будем обозначать монеты, которые во время текущего взвешивания следует положить на весы, причем, если монета на весах уже была, то на ту же самую чашу, на которой эта монета находилась во время своего предыдущего взвешивания. Знаком “-“ будем обозначать монеты, которые следует переложить на противоположную чашу весов, по отношению к той, на которой они находились (каждая в отдельности), заметим, что если монета на весах еще не была, то знак “-“ к ней применен быть не может. Наконец, знаком “0” — монеты, которые в очередном взвешивании не участвуют. Тогда, существует 14 различных способов пометки монет для трех взвешиваний:
Из полученной таблицы вычеркнем 2 столбца так, чтобы в каждой из трех строк количество ненулевых элементов оказалось четным (ведь мы не можем во время одного взвешивания положить на две чаши весов нечетное число монет). Это могут быть, например, столбцы 4 и 14. Теперь будем взвешивать 12 монет так, как это записано в оставшихся 12 столбцах. То есть, в первом взвешивании будут участвовать 8 произвольных монет, во втором — три монеты следует с весов убрать, две — переложить на противоположные по отношению к первому взвешиванию чаши весов и три монеты положить на весы впервые (на свободные места так, чтобы на каждой из чаш вновь оказалось по 4 монеты). Согласно схеме проведем и третье взвешивание, опять располагая на каждой чаше весов по 4 монеты. Результат каждого взвешивания в отдельности никак не анализируется, а просто записывается. При этом равновесие на весах всегда кодируется нулем, впервые возникшее неравновесное состояние — знаком плюс, если при следующем взвешивании весы отклонятся от равновесия в ту же самую сторону, то результат такого взвешивания также кодируется плюсом, а если в другую сторону — то минусом. Например, записи “= >” кодируются как “0++”, а записи “ ” и “>= N>2 количество взвешиваний при определяется по формуле round(log3(2*N + 1)) (за одно взвешивание задача не разрешима ни для какого количества монет. ), но подход к решению задачи при этом не изменится.
Попробуйте теперь решить задачу, которая предлагалась в 1998 году на уже упоминавшемся выше полуфинале чемпионата мира по программированию среди студенческих команд вузов. В ней также требовалось определить номер фальшивой монеты, вес которой отличался от остальных. Но все взвешивания уже были проведены, а их результаты записаны. Число взвешиваний являлось входным параметром в задаче (оно могло быть и избыточным по сравнению с описанным выше оптимальным алгоритмом определения номера фальшивой монеты). При этом в каждом из взвешиваний могло участвовать любое четное количество имеющихся монет (сколько и какие именно — известно). Результаты записывались с помощью символов “ ” и “=”.
Еще одна задача на взвешивания рассмотрена в [8]. В общем случае в ней требуется найти набор из минимального количества гирь такой, что с его помощью можно взвесить любой груз, весящий целое число килограмм, в диапазоне от 1 кг до N кг. При необходимости гири можно располагать на обеих чашах весов. Так, для N=40 это гири 1, 3, 9 и 27 кг.
Поиск подстроки в строке
Формализовать эту задачу можно следующим образом. Пусть задан массив s из N элементов (строка) и массив p из M элементов (подстрока), причем 0 p в s . Эта задача на практике встречается очень часто. Так, в большинстве текстовых редакторов реализована операция поиска по образцу, которая практически полностью совпадает с описанной задачей. Если размер массива s — N не превосходит 255, а тип его элементов — char, то в Турбо Паскале такой поиск можно выполнять с помощью стандартной функции Pos(p,s) . Однако, в общем случае ее приходится реализовывать самостоятельно. Прямой поиск, основанный на последовательном сравнении подстроки сначала с первыми M символами строки, затем с символами с номерами 2 — M+1 и т. д., в худшем случае произведет порядка N*M сравнений. Но для этой задачи известен алгоритм Боуера и Мура, который для произвольных строк выполняет не намного более N/M сравнений. То есть разница в вычислительной сложности составляет M^2 Рассмотрим последний алгоритм, на примере которого также можно показать, что использование небольшого количества дополнительной памяти (в данном случае вспомогательного массива, размер которого равен размеру алфавита строк) позволяет существенно ускорить выполнение программы.
Перед фактическим поиском, для всех символов, которые могут встретиться в строке, вычисляется и запоминается в массиве d расстояние от самого правого вхождения этого символа в искомую подстроку до ее конца. Если же какого-то символа из алфавита строки в подстроке нет, то такое расстояние считается равным длине подстроки M. Посимвольное же сравнение подстроки с некоторым фрагментом строки начинается не с начала, а с конца искомой подстроки (образца). Если какой-либо символ образца не совпадает с соответствующим символом фрагмента строки, а х —последний символ фрагмента строки, то образец можно сдвинуть вдоль строки вправо на d[x] символов. Если большинство символов в строке отличны от символов подстроки, то сдвиг будет происходить на M элементов, что и обеспечит приведенную выше сложность алгоритма. Покажем работу алгоритма на примере поиска слова коала в строке:
кокаколулюбитикоала.
коала
коала
коала
коала
коала
Здесь выделены жирным символы, которые участвовали в сравнениях. Сдвиги определялись такими значениями массива d: d['к']=4, d['л']=1, d['ю']=5 . Если бы последней в рассматриваемом фрагменте строки оказалась буква а, то величина сдвига была бы равна 2, так как в образце есть еще одна такая буква, отстоящая от конца на 2 символа, а при ее отсутствии сдвиг был бы равен 5. Приведем теперь возможную реализацию описанного алгоритма, для простоты считая, что размер подстроки не превосходит 255, что не снижает общности этой программы:
Приведенный алгоритм не дает выигрыша только в одном случае — когда количество частичных совпадений искомой подстроки с фрагментами текста достаточно велико. Это возможно, например, при чрезвычайной ограниченности алфавита, из символов которого составляются строки. Тогда следует применять алгоритм Кнута-Мориса-Пратта, или комбинацию из двух алгоритмов.
Рассмотренную проблему не следует путать с такой задачей. Пусть задан массив s из N элементов и массив p из M элементов, причем 0<M<=N . Требуется выяснить, можно ли из первого массива вычеркнуть некоторые члены так, чтобы он совпал со вторым. Число операций в данном случае имеет порядок N + M .
Какой оптимальный алгоритм поиска в произвольном массиве
Какой оптимальный алгоритм поиска в произвольном массиве
В настоящее время разработано множество методов поиска элементов в массиве и их сортировки [1]. В данной статье предложен ряд алгоритмов, которые повышают быстродействие поиска и сортировки:
1) алгоритм поиска в произвольном массиве, использующий мультипликативный критерий
2) алгоритм поиска в упорядоченном массиве методом аппроксимации
3) техника избежания логических сравнений, которая позволяет увеличить скорость некоторых сортировок и находить экстремумы в массиве за минимальное время
4) концепция сложной организации данных в многомерном массиве
Все эти идеи объединены общим принципом, который составляет их суть: мы добиваемся более быстрого и эффективного решения самых разных задач с помощью некоторых математических приемов. Эти хитроумные средства – своего рода толика волшебства в варево стандартных логических методов. Фактически речь идет о формировании особого стиля программирования, возможности которого далеко не исчерпываются настоящей статьей. Важно подчеркнуть, что эффективность предлагаемых методов во многом зависит от архитектуры используемой машины. И это совершенно естественно: техническая реализация ЭВМ должна приспосабливаться к логике программ и наиболее эффективным решениям, а не наоборот.
Работа происходит на одномерном массиве M[1..N], который состоит из N неповторяющихся элементов (ключей). Через x обозначен искомый ключ.
2. Алгоритм поиска в массиве, использующий мультипликативный критерий
Идея алгоритма. Поскольку в неотсортированном массиве у нас нет никаких критериев для определения порядкового номера элемента, совпадающего с ключом x, единственным способом поиска является последовательный перебор. Однако он может быть улучшен за счет того, что на каждом шаге цикла будет проверяться на равенство с x не один элемент, а сразу несколько. Для этого достаточно воспользоваться следующим правилом: выражение (M[1]-x)*(M[2]-x)*. *(M[d]-x) обращается в нуль тогда и только тогда, когда хотя бы один из элементов M[1], M[2], . M[d] равен x.
В рассмотренном ниже примере алгоритма, записанном на языке Pascal, имеем: количество рассматриваемых за один шаг элементов d равно 4; для сокращения количества сравнений в операторе цикла используется барьер – дополнительный элемент M[n+1], в который записывается искомый ключ. Очевидно, что объем массива должен быть не меньше n+d, где n – количество зарезервированных ячеек, d – количество рассматриваемых за один шаг элементов, иначе возможна ошибка выхода за границы массива.
Данный алгоритм имеет ту же временную сложность, что и последовательный перебор. При этом эффективность предложенного алгоритма во многом зависит от того, будут ли в используемом компьютере операции вычитания и умножения осуществляться быстрее логического сравнения. Еще лучше, если язык программирования позволяет использовать побитовое исключающее ИЛИ между x и M[i] вместо вычитания и непобитовое И вместо умножения.
3. Алгоритм поиска в упорядоченном массиве методом аппроксимации
Идея алгоритма. Алгоритм основан на том, что упорядоченный по возрастанию массив содержит элементы, расположенные в интервале [M[1]; M[N]]. Искомое число x также предположительно находится в нем. Припишем интервалу [M[1]; M[N]] своего рода процентную шкалу, разделив его на одинаковые участки. Если сопоставить x с числами M[1] и M[N], то можно приблизительно установить тот «процент», на который приходится x. Чем равномернее распределены элементы в массиве или эквивалентные им точки на отрезке, тем точнее приближение. Ниже представлен укрупненное описание метода:
1. Если x меньше M[1] или больше M[N], поиск завершен.
2. Помещаем в ячейку N+1 значение x+1 в качестве барьера.
3. Вычисляем приблизительное положение x в диапазоне [M[1]; M[N]] по формуле
где модульные скобки означают округление результата до целой части и изменение знака на плюс, если результат отрицательный. Если индексация массива начинается с произвольного числа С, следует использовать формулу вида:
4. Увеличиваем i, пока M[i] x.
6. Если M[i]=x, элемент найден, иначе элемента в массиве нет.
Реализация рассмотренного алгоритма на языке Pascal имеет вид:
1. Если N и x – большие числа, произведение N*(x-M[1]) может дать результат, выходящий за пределы разрядной сетки объявленного типа. Поэтому рекоммендуется сначала производить деление, как это показано в представленном алгоритме. В крайнем случае можно несколькими итерациями бинарного поиска сократить диапазон, в котором предположительно находится x. Это уменьшит входящие в формулу значения.
2. Быстродействие алгоритма «аппроксимацией» зависит только от степени равномерности распределения элементов в массиве. Так, поиск в массиве, имеющем достаточно равномерное распределение ключей 1 , выполняется в 2-3 раза быстрее бинарного поиска уже для n=100. В отличие от поиска хешированем рассмотренный алгоритм не требует выделения дополнительной памяти под хеш-массив.
4. Способ уменьшить количество логических сравнений
При решении многих задач встречается следующая необходимость: сравнить значения в i и j ячейках массива M; если при этом оказывается, что порядок возрастания элементов в массиве нарушен (например, при i > j, M[i] 2 .
Схожая конструкция логического сравнения с присваиванием используется также в сортировке выбором и некоторых других сортировках, а также при поиске экстремумов-значений в массиве, как это показано в следующем примере:
Эти алгоритмы тоже могут быть улучшены описанным методом. Временная сложность поиска экстремума должна снизиться благодаря этому почти вдвое:
13.Методы поиска в массиве
Если у нас есть массив, содержащий упорядоченную последовательность данных, то очень эффективен двоичный поиск.
Переменные Lb и Ub содержат, соответственно, левую и правую границы отрезка массива, где находится нужный нам элемент. Мы начинаем всегда с исследования среднего элемента отрезка. Если искомое значение меньше среднего элемента, мы переходим к поиску в верхней половине отрезка, где все элементы меньше только что проверенного. Другими словами, значением Ub становится (M – 1) и на следующей итерации мы работаем с половиной массива. Таким образом, в результате каждой проверки мы вдвое сужаем область поиска. Так, в нашем примере, после первой итерации область поиска – всего лишь три элемента, после второй остается всего лишь один элемент. Таким образом, если длина массива равна 6, нам достаточно трех итераций, чтобы найти нужное число.
Двоичный поиск — очень мощный метод. Если, например, длина массива равна 1023, после первого сравнения область сужается до 511 элементов, а после второй — до 255. Легко посчитать, что для поиска в массиве из 1023 элементов достаточно 10 сравнений.
Кроме поиска бывает нужно вставлять и удалять элементы. К сожалению, массив плохо приспособлен для выполнения этих операций. О повышении эффективности операций вставки/удаления можно прочитать в разделе про структуры данных.
Частным случаем двоичного поиска является метод бисекции, который применяется для поиска корней заданной непрерывной функции на заданном отрезке.
Линейный, последовательный поиск — алгоритм нахождения заданного значения произвольной функции на некотором отрезке. Даный алгоритм является простейшим алгоритмом поиска и в отличие, например, от двоичного поиска, не накладывает никаких ограничений на функцию и имеет простейшую реализацию. Поиск значения функции осуществляется простым сравнением очередного рассматриваемого значения (как правило поиск происходит слева направо, то есть от меньших значений аргумента к большим) и, если значения совпадают (с той или иной точностью), то поиск считается завершённым.
14. Методы внутренней сортировки
сортиро́вка пузырько́м (англ. bubble sort) — простой алгоритм сортировки. Для понимания и реализации этот алгоритм — простейший, но эффективен он лишь для небольших массивов. Сложность алгоритма: O(n²).
Алгоритм считается учебным и практически не применяется вне учебной литературы, вместо него на практике применяется сортировка вставками.
Пример сортировки пузырьком списка случайных чисел.
Алгоритм состоит в повторяющихся проходах по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При проходе алгоритма, элемент, стоящий не на своём месте, «всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма.
Сортировка перемешиванием (Шейкерная сортировка) (англ. Cocktail sort) — разновидность пузырьковой сортировки. Анализируя метод пузырьковой сортировки можно отметить два обстоятельства.
Во-первых, если при движении по части массива перестановки не происходят, то эта часть массива уже отсортирована и, следовательно, ее можно исключить из рассмотрения.
Во-вторых, при движении от конца массива к началу минимальный элемент “всплывает” на первую позицию, а максимальный элемент сдвигается только на одну позицию вправо.
Эти две идеи приводят к следующим модификациям в методе пузырьковой сортировки. Границы рабочей части массива (т.е. части массива, где происходит движение) устанавливаются в месте последнего обмена на каждой итерации. Массив просматривается поочередно справа налево и слева направо.
Лучший случай для этой сортировки — отсортированный массив (О(n)), худший — отсортированный в обратном порядке (O(n²)).
Сортировка вставками — простой алгоритм сортировки. Хотя этот метод сортировки намного менее эффективен, чем более сложные алгоритмы (такие как быстрая сортировка), у него есть ряд преимуществ:
прост в реализации;
эффективен на небольших наборах данных, на наборах данных до десятков элементов может оказаться лучшим;
эффективен на наборах данных, которые уже частично отсортированы;
это устойчивый алгоритм сортировки (не меняет порядок элементов, которые уже отсортированы);
может сортировать список по мере его получения;
не требует временной памяти, даже под стек.
На каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированном списке, до тех пор пока набор входных данных не будет исчерпан. Метод выбора очередного элемента из исходного массива произволен; может использоваться практически любой алгоритм выбора. Обычно (и с целью получения устойчивого алгоритма сортировки), элементы вставляются по порядку их появления во входном массиве. Приведенный ниже алгоритм использует именно эту стратегию выбора.
Сортировка слиянием (англ. merge sort) — алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например — потоки) в определённом порядке. Эта сортировка — хороший пример использования принципа «разделяй и властвуй». Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи.
Для решения задачи сортировки эти три этапа выглядят так:
1) Сортируемый массив разбивается на две части примерно одинакового размера;
2) Каждая из получившихся частей сортируется отдельно, например — тем же самым алгоритмом;
3) Два упорядоченных массива половинного размера соединяются в один.
Рекурсивное разбиение задачи на меньшие происходит до тех пор, пока размер массива не достигнет единицы (любой массив длины 1 можно считать упорядоченным).
Сортировка с помощью двоичного дерева (сортировка двоичным деревом, сортировка деревом, древесная сортировка, сортировка с помощью бинарного дерева, англ. tree sort) — универсальный алгоритм сортировки, заключающийся в построении двоичного дерева поиска по ключам массива (списка), с последующей сборкой результирующего массива путём обхода узлов построенного дерева в необходимом порядке следования ключей. Данная сортировка является оптимальной при получении данных путём непосредственного чтения с потока (например с файла, сокета или консоли).
Какой оптимальный алгоритм поиска в произвольном массиве
Рассмотрим сначала нюансы реализации “технических” задач поиска, которые встречаются в различных алгоритмах. Начнем с, казалось бы, тривиальной задачи поиска элемента в неупорядоченном массиве. Во всех примерах, относящихся к поиску в одномерном массиве будем использовать следующую переменную a:
при этом собственно элементы массива, которые мы будем рассматривать, пронумерованы от 1 до N, а нулевой элемент будем использовать как вспомогательный в случае необходимости. Конкретный же тип элемента в большинстве описываемых алгоритмов не важен, он может быть как любым числовым, так и символьным или даже строковым. Алгоритм поиска в массиве элемента, значение которого равно K, может выглядеть так:
При отсутствии в массиве элемента с искомым значением K печатается значение нулевого индекса. Оказывается, что и такую достаточно простую программу можно упростить, заодно продемонстрировав так называемый “барьерный” метод, который часто применяется в программировании в том числе и олимпиадных задач. В данном случае он заключается в том, что мы можем занести в дополнительный элемент массива (например, нулевой) искомое значение K, избавившись тем самым в условии окончания цикла от проверки на выход за границу массива:
Эта программа не просто проще и эффективней. В ней практически невозможно сделать ошибку. Другой полезный прием можно показать на задаче поиска максимального и минимального значения в массиве. Состоит он в том, что при любом поиске в массиве искать следует не значение искомого элемента, максимума, минимума и т.п., а его индекс. Тогда решая одну задачу, мы по сути дела решаем сразу две: определяем не только наличие искомого элемента, значение максимума или минимума, но и их местоположение в массиве. Программа при этом не только не усложняется, но зачастую становится даже короче:
Заметим, что использование в качестве начальных значений для минимума и максимума не значение первого элемента массива, а максимальное и минимальное значение в типе элементов, может привести к ошибке. Так, следующая программа не находит значение максимума для убывающего массива целых чисел (. ):
Казалось бы на этом рассмотрение алгоритмов поиска в неупорядоченном массиве можно завершить. Однако именно с одновременного поиска минимума и максимума можно начать класс алгоритмов поиска, более эффективных, чем приведенные выше стандартные алгоритмы. Причем именно при решении олимпиадных задач их знание может пригодиться в первую очередь. Итак, в приведенном выше алгоритме поиска максимального и минимального элемента в массиве в худшем случае выполняется 2N – 2 сравнений.Покажем, что ту же задачу можно решить за 3[N/2] – 2 сравнения*. Пусть у нас имеется четное число элементов. Разобьем их на пары и в каждой из N/2 пар за одно сравнение определим, какой элемент больше, а какой меньше. Тогда максимум можно искать уже любым способом только из наибольших элементов в парах, а минимум — среди наименьших. Общее число сравнений при этом равно N/2 + 2(N/2 – 1) = 3N/2 – 2. Для нечетного числа элементов — элемент, не попавший ни в одну из пар, должен участвовать как в поиске максимума, так и минимума.
Еще большей эффективности можно добиться при одновременном поиске максимального и второго по величине числа. Для этого организуем поиск максимума по схеме “теннисного турнира”, а именно: разобьем элементы на пары и определим в каждой из пар больший элемент, затем разобьем на пары уже эти элементы и т.д. В “финале” и будет определен максимум. Количество сравнений в таком алгоритме, как и в традиционной схеме, равно N – 1. Однако, максимальный элемент участвовал при этом в [log2N] сравнениях, причем одно из них проходило обязательно со вторым по величине элементом. Таким образом, теперь для поиска этого элемента потребуется всего [log2N] – 1 сравнение (. ). Попробуйте самостоятельно построить эффективный алгоритм для поиска уже первых трех по величите элементов.
В данном контексте можно поставить также задачу поиска i-го по счету элемента, называемого i-ой порядковой статистикой. Кроме максимума и минимума, специфической порядковой статистикой является медиана — элемент с номером (N + 1)/2 для нечетных N и два соседних элемента для четных. Конечно, задачу поиска любой порядковой статистики можно решить, предварительно отсортировав массив. Но, как будет показано ниже, оптимальные по количеству сравнений универсальные (то есть пригодные для произвольных массивов) алгоритмы сортировки выполняют порядка Nlog2N сравнений. А задачу поиска i-ой порядковой статистики можно решить, производя O(N) сравнений. Алгоритм, который гарантирует эту оценку достаточно сложен, он подробно изложен в [1, 2, 3]. Мы же приведем схему алгоритма, который в худшем случае не является линейным, однако на практике работает существенно быстрее, следовательно именно его и нужно использовать в практике реального программирования:
Алгоритм Выбор(A, L, R, i) 1. if L=R then результат – A[L], конец; 2. Q:=L+random(R-L+1) 3. Переставляем элементы от L до R в A так, чтобы сначала шли элементы, меньшие A[Q], а затем все остальные, первый элемент во второй группе обозначим K. 4. if i⇐(K-L) then Выбор(A, L, K-1, i) else Выбор(A, K, R, i-(K-L)) 5. конец.
Оптимальную реализацию пункта 3 можно заимствовать из алгоритма так называемой быстрой сортировки. Наконец, рассмотрим задачу поиска в последовательности из N чисел, хранения которой не требуется вообще, следовательно ее длина может быть очень велика. Пусть известно, что в этой последовательности встречаются по одному разу все числа от 0 до N, кроме одного. Это пропущенное число и требуется найти. Вот возможное решение такой задачи:
Данную программу легко переписать так, чтобы она работала и для значений N, превосходящих максимальное представимое целое число. Для этого следует использовать переменные типа extended, а цикл for заменить на while. Используя аналогичный прием попробуйте решить следующую задачу. Пусть N — количество чисел, нечетно и известно, что среди вводимых чисел каждое имеет ровно одно, равное себе, а одно число — нет. Найдите это число. (Указание. В данном случае можно воспользоваться свойством логической функции “исключающее или”, обозначаемой в Паскале как xor: a xor b xor b = a.)
Сноски: Обозначение [] соответствует для неотрицательных чисел округлению до ближайшего целого числа, большего или равного выражению в указанных скобках, в отличие от целой части, где округление производится до ближайшего целого, меньшего или равного рассматриваемому выражению.
Создание лабиринта
Глава 4 Лабиринты
В лабиринте у вас, по крайней мере, есть цель.
Мне нравится эта тема. С одной стороны, она занимательна, с другой — полезна (я надеюсь, что вы найдете не одно и не два применения алгоритмам, описанным в этой части книги), а с третьей — даже научна. Лабиринты, выражаясь математическим языком — это графы; все алгоритмы, которые мы рассмотрим, соответственно, являются алгоритмами на графах. Графам же посвящена целая теория в математике (она так и называется: теория графов). Недаром два алгоритма, с которыми вы познакомитесь в этой главе, носят имена Прима (Prim) и Краскала (Kruskal) — очень известных в теории графов людей.
Итак, сейчас мы займемся лабиринтами. Если говорить более конкретно, в область наших интересов входят следующие задачи:
Представление лабиринтов в памяти
Толковый словарь русского языка определяет лабиринт как «запутанную сеть дорожек, ходов, сообщающихся друг с другом помещений». Пожалуй, это определение слишком неконкретное и чересчур общее для наших целей. Сразу скажу, что наши лабиринты — плоские (двумерные, если угодно), поэтому их можно легко нарисовать на бумаге. Кроме того, все помещения (их обычно называют локациями) будут квадратными, а сам лабиринт (естественно) — прямоугольным. У каждого такого помещения есть не более четырех соседних, и в каждое соседнее помещение может вести проход (а может и не вести — в этом случае там будет «стена»). Думаю, проще всего посмотреть на пример (рис. 4.1).
Рис. 4.1. Пример лабиринта
Именно с лабиринтами такого типа мы и будем работать. Следующий вопрос — как представить лабиринт в памяти компьютера. Заманчиво просто создать двумерный массив из нулей и единиц: нуль будет обозначать стену, единица — проход (рис. 4.2).
Рис. 4.2. Простое представление лабиринта в памяти
Надо только при выводе на экран рисовать стенки тонкими линиями (я не стал этого делать для наглядности) — и все. Этот способ, в принципе, позволяет описать любой лабиринт «нашего» типа. К сожалению, есть у него и существенный недостаток: если разрушить любую стену (то есть поменять нуль на единицу), в лабиринте образуется новая локация на месте разрушенной стены. Сейчас это, вроде бы, и не имеет значения, однако для алгоритмов генерации лабиринтов, которые мы изучим, подобное поведение недопустимо. При разрушении стены должен открываться проход, но никак не образовываться новая локация. Поэтому нам придется воспользоваться не столь простым и удобным, зато лишенным этого недостатка методом.
В каждой локации лабиринта нас интересует информация о стенах/проходах. В локации может существовать от одной до четырех стен (сверху, снизу, слева и справа). Поэтому разумно задавать локацию записью:
type Location = record
На первый взгляд процедура кажется довольно громоздкой, но если присмотреться, то становится ясно, что ядро у нее не такое уж большое. Для реализации процедуры мне потребовались две дополнительные функции: CanGo() и Solve(). Функция CanGo() определяет, есть или нет стены между локациями (x, y) и (x + dx, y + dy) (то есть можно ли пройти из одной в другую). При этом предполагается, что локации находятся по соседству — первая расположена сверху, слева, снизу или справа от второй. Функция Solve() более интересна и сложна. Ей передается три параметра — координаты текущей локации и номер шага. Номер нужен для того, чтобы знать, в какую строчку «бортового журнала» записывать текущее движение. Дальше все происходит по алгоритму, о котором мы говорили выше:
пометить текущую локацию как посещенную
добавить ее в «бортовой журнал»…
Обратите внимание на «признак конца». Нам как-то надо отмечать конец журнала. Поскольку локации с координатами (-1, -1) не существует, эту «псевдолокацию» вполне можно использовать. если локация найдена — конец алгоритма
исследуем каждую свободную дорожку Вот здесь я применил небольшую хитрость: всего из каждой локации может вести максимум четыре разные дорожки. Первая начинается от соседней сверху локации, вторая — от левой, третья — от нижней, а четвертая — от правой.
Чтобы не писать четыре раза
исследовать_дорожку(x, y – 1)
исследовать_дорожку(x – 1, y)
исследовать_дорожку(x, y + 1)
исследовать_дорожку(x + 1, y)
я воспользовался циклом (не забывайте, что исследовать_дорожку() — это не вызов процедуры, а фрагмент из нескольких строк кода, поэтому экономия заметная):
Если решение найдено, то работа алгоритма заканчивается; в противном случае текущая локация помечается как непосещенная и происходит выход из процедуры. Обратите внимание, что каждый шаг в лабиринте — это рекурсивный вызов. Такое решение позволяет легко вернуться на шаг назад (помните, это важная часть алгоритма) — для этого надо всего лишь выйти из функции, сообщив при этом вызывающей функции, что решение не найдено. Главная процедура делает не так уж и много работы: она инициализирует массивы, затем вызывает Solve() и рисует на экране полученное решение (рис. 4.4). В примере я выбрал верхнюю левую локацию лабиринта как стартовую, а верхнюю правую — как финишную.
Обратите также внимание на строку:
Если текущая локация находится на краю или в углу лабиринта, числа x + dx[i] и y + dy[i] могут оказаться некорректными индексами массива Visited (то есть попросту указывать на локацию, лежащую за границами лабиринта). Ошибки не возникает потому, что Delphi по умолчанию использует так называемую сокращенную схему вычисления логических выражений: если значение CanGo() оказалось равно false, нет нужды вычислять правую часть выражения (после and) — и так ясно, что значение всего выражения будет равно false. Если функция CanGo() определит, что мы пытаемся выйти за пределы лабиринта, она, естественно, вернет false, поскольку весь лабиринт ограничен стеной; следовательно, правая часть выражения в таких случаях никогда не будет вычисляться. Мы будем пользоваться этой особенностью Delphi и в дальнейшем.
Рис. 4.4. Решение, найденное с помощью рекурсивного обхода
Надеюсь, принцип работы рекурсивного обхода более или менее ясен. Возможно, стоило подробнее на нем остановиться и постараться объяснить все тонкости более доходчиво (если алгоритм рекурсивен, он уже не слишком прост — по крайней мере, для меня), однако мне просто жаль на него времени. Сейчас я подробно распишу недостатки рекурсивного обхода, а потом мы рассмотрим куда более передовой алгоритм волновой трассировки.
Итак, два недостатка алгоритма лежат на поверхности:
Третий недостаток гораздо более существенный, хотя и проявляется он не всегда. Посмотрите на лабиринт, изображенный на рис. 4.5.
Линейный и двоичный поиски в упорядоченном массиве
Массив одна из самых популярных структур данных и в тоже время, самых старых. С их помощью можно решать многие задачи связанный с хранением, поиском, удалением и добавлением данных. В Java массив представляет собой ссылку на область память, где хранятся данные массива.
Упорядоченный массив, представляет собой массив, в котором его элементы расположены в упорядоченном виде (по возрастанию/убыванию). Такие массивы используются в тех случаях, если при работе с ним, количество операций поиска элемента массива много больше операций вставок и удаления. Далее вы поймете почему.
И так, для поиска определенного элемента в массиве используют алгоритмы линейного и двоичного поиска. Рассмотрим каждый из них подробно для случая упорядоченного массива.
Алгоритм линейного поиска в упорядоченном массиве.
По сути алгоритм линейного поиска работает одинаково для упорядоченного и неупорядоченного массивов. Его суть заключается в последовательном переборе массива, начиная с первого(нулевого) элемента до тех пор, пока не будет найден нужный элемент. Стоит отметить, что этот алгоритм является эффективным для небольших массивов. Однако на практике в реальных прикладных программах такие случи довольно редки.
Заметим, что в среднем алгоритм работает за линейное время O(N).
Алгоритм двоичного поиска в упорядоченном массиве.
В отличии от линейного, алгоритм двоичного поиска эффективен только в упорядоченном массиве, однако скорость выполнения не так сильно зависит от размера массива. Даже можно сказать, что алгоритм двоичного поиска создан для поиска в массивах больших размеров.
Реализация алгоритма представляет собой известную игру “Угадай число”. Например, кто-то загадывает число от 0 до 100 (пусть будет 20), а вам нужно угадать число. Вы говорите 50, а в ответ слышите “меньше”, вы говорите “25”, ответ “меньше”, вы – “13” – “больше”, и т.д. пока не угадаете. Очевидно, что при каждой итерации мы уменьшаем выборку в два раза и так каждый раз. Мы выбираем среднее число между двумя концами и спрашиваем, больше оно или меньше искомого и исходя из ответа меняем концы выборки и повторяем.