Какой оптимальный алгоритм поиска в произвольном массиве

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) — универсальный алгоритм сортировки, заключающийся в построении двоичного дерева поиска по ключам массива (списка), с последующей сборкой результирующего массива путём обхода узлов построенного дерева в необходимом порядке следования ключей. Данная сортировка является оптимальной при получении данных путём непосредственного чтения с потока (например с файла, сокета или консоли).

Самый эффективный способ поиска в массивах?

Есть 2 масива(очень больших). Искомое значение (только одно) находится в одном из них. Нужен какой-то хороший алгоритм поиска.

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

Насколько эффективным было бы запускать поиск по 2 массивам одновременно с точки зрения производительности?

Цель найти оптимальный способ (наименее ресурсоёмкий и наиболее быстрый).

Какие алгоритмы поиска будут эффективными в такой ситуации?

Для поиска строк самая быстрая структура — тернарное дерево. Любые другие варианты будут заведомо хуже, и их в этом контексте обсуждать нет смысла.

Реализации для JS есть, например tritium. Из примеров оттуда:

Для решения Вашей задачи можно предложить несколько методов: бинарный поиск по полиномиальному хэшу, префиксное дерево.

Полиномиальные хэши. Хэш-функция — это отображение, ставящее в соответствие некоторому объекту число. В нашем случае — строку. Полиномиальные хэши — это полином. Вообще говоря, можно брать любые функции. Но в таком случае может оказаться, что для двух элементов (строк) у нас есть два одинаковых объекта. Полиномиальные функции сводят этот риск в минимум. Считаются они так:

где строка[i] — код символа.

Как можно заметить, здесь происходит много вычислений со степенями. Это не есть хорошо. Если нужна скорость, то можно применить быстрое возведение в степень. Кроме того, оказывается, что большие степени — это большие числа, меньшая скорость и больше памяти, поэтому полиномиальный хэш можно брать по модулю:

[f(строка)]_k , где k — большое простое число, а операция [.] — взятие остатка от деления. Подробнее тут, здесь и вот здесь.

Замечу, что взятие остатка от деления можно проводить от каждого слагаемого отдельно:

Таким образом, посчитав хэши, упорядочим строки по нему. После чего сделаем сортировку по хэшу. В отсортированном массиве можно искать нужный элемент бинарным поиском. Тогда время работы O(max(log N, log M)), где M, N — длины строк.

Префиксное дерево Данное дерево содержит все префиксы строк. Тогда можем осуществить поиск в дереве за O(max(максимальная длина строки)).

Arrays, Collections: Алгоритмический минимум

Недавно на собеседовании в крупную компанию на должность Java разработчика меня попросили реализовать стандартный алгоритм сортировки. Поскольку я никогда не реализовывал самописные алгоритмы сортировки, а пользовался всегда готовыми решениями, у меня возникли затруднения с реализацией. После собеседования я решил разобраться в вопросе и подготовить список основных алгоритмов сортировки и поиска, которые используются в стандартном пакете java — Java Collections Framework (JCF). Для этого я изучил исходники Oracle JDK 7.80 (UPD: добавлена ссылка).

В самом обобщенном виде результат изучения представлен на рисунке. Подробности — в основном тексте.

Рисунок 1. Методы Arrays, Collections и реализуемые ими алгоритмы

Первое, что поразило меня в алгоритмах, реализованных в Arrays и Collections — то, что их можно буквально по пальцам пересчитать — по большому счету, это два алгоритма сортировки и один алгоритм поиска.

Второе — то, что сортировка списков «под капотом» использует сортировку массивов.

Третье — то, что один из алгоритмов сортировки портирован с python.

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

Алгоритм сортировки слиянием, который является основным для сортировки массивов ссылочных типов, буквально назван по имени своего создателя Tim Peters — TimSort. Этот алгоритм был адаптирован Джошуа Блохом с алгоритма сортировки списков, реализованном на python Тимом Петерсом.

Кратко излагая результаты, стоит отметить, что:

1. Можно условно выделить три слоя методов:
   • Методы API
   • Методы базовых (основных) алгоритмов
   • Методы (блоки) дополнительных алгоритмов
2. Основных алгоритмов используется три. Два алгоритма сортировки: быстрая сортировка, сортировка слиянием. Один алгоритм поиска: бинарный поиск.
3. Для оптимизации «основные» алгоритмы заменяются на более подходящие в данный момент “дополнительные” алгоритмы (полный список алгоритмов и условий переключения приведен в конце)
4. Для определения того, какой из «дополнительных» алгоритмов будет задействован, могут использоваться:
   • сигнатуры методов (типы аргументов, булевы переменные)
   • флаги VM
   • пороговые значения длины массива/списка, хранящиеся в приватных переменных классов

Итак, для того, чтобы выяснить, какие основные и дополнительные алгоритмы используются в пакете util, нужно разобрать реализацию 4-х методов из API Collections и API Arrays.

Таблица 1. API Arrays vs API Collections

Arrays.sort

Массивы примитивных типов

Основной алгоритм сортировки для массивов примитивных типов в Arrays — быстрая сортировка. Для реализации этой сортировки выделен финальный класс DualPivotQuickSort, который предоставляет публичные методы sort для сортировки массивов всех примитивных типов данных. Методы Arrays API вызывают эти методы и пробрасывают в них ссылку на массив. Если требуется отсортировать определенный диапазон массива, то передаются еще и индексы начала и конца диапазона.

Временная сложность алгоритма быстрой сортировки в лучшем случае и в среднем случае составляет O(n log n). В некоторых случаях (например, на малых массивах) алгоритм быстрой сортировки обладает не лучшей производительностью, деградирует до квадратичной сложности. Поэтому имеет смысл вместо него применять другие алгоритмы, которые в общем случае проигрывают, но в конкретных случаях могут дать выигрыш. В качестве дополнительных алгоритмов были выбраны сортировка вставками, “обычная” быстрая сортировка (с одной опорной точкой), сортировка подсчетом.

Инженеры Oracle эмпирическим путем вычислили оптимальные размерности массивов для задействования каждого дополнительного алгоритма сортировки. Эти значения записаны в приватных полях класса DualPivotQuickSort. Для наглядности я свел их в таблицу 2.

Таблица 2. Дополнительные алгоритмы в DualPivotQuickSort.sort

В теле методов DualPivotQuickSort.sort производятся проверки на длину массива, и в зависимости от результата применяется либо основной, либо дополнительный алгоритм.

Массивы примитивных типов. Выбор алгоритма и булев параметр leftmost

Параметр leftmost при необходимости передается в метод sort и показывает, является ли указанная часть самой левой в диапазоне. Если да, то применяется алгоритм “обычной” сортировки вставками. Если нет, то применяется парная сортировка вставками.

Еще одно объяснение о выборе дополнительных алгоритмов можно почитать
здесь.

Массивы ссылочных типов

Для массивов ссылочных типов в качестве основного предусмотрен алгоритм сортировки слиянием, он реализован в трех вариациях. Две актуальные реализации вынесены в специальные классы: TimSort, ComparableTimSort. TimSort предназначена для сортировки объектов с использованием компараторов. ComparableTimSort — это версия TimSort, предназначенная для сортировки объектов, поддерживающих Comparable. Подробности реализации сортировки TimSort смотрите в посте на хабре.

Класс TimSort содержит единственную пороговую величину, при сравнении с которой принимается решение о переключении на дополнительный алгоритм. Это величина называется MIN_MERGE и хранит минимальную длину массива, при которой будет производиться сортировка слиянием. Если же длина массива будет меньше MIN_MERGE, т.е. 32, то будет задействована бинарная сортировка вставками. Как сказано в документации, это мини-TimSort, т.е. без использования слияний.

Таблица 3. Дополнительные алгоритмы в TimSort.sort и ComparableTimSort.sort

Третья реализация сортировки слиянием является legacy и оставлена для сохранения обратной совместимости с версией JDK 1.6 и более ранними. Legacy сортировка обернута в метод legacyMergeSort и непосредственно реализована в методе Arrays.mergeSort. Для того, чтобы ее использовать, необходимо выставить флаг -Djava.util.Arrays.useLegacyMergeSort=true перед запуском виртуальной машины. Для хранения значения этой переменной в Arrays имеется внутренний статический класс LegacyMergeSort (см. Листинг. 1).

Листинг 1. Статический внутренний класс LegacyMergeSort в Arrays

При вызове Arrays.sort с массивом ссылочного типа происходит проверка, выставлен ли флаг на применение legacy сортировки. Тогда происходит вызов либо legacy сортировки, либо одной из базовых (см. Листинг 2).

Листинг 2. Реализация метода Arrays.sort для массива ссылочного типа с компаратором

Arrays.binarySearch

Для массивов как примитивных, так и ссылочных типов предусмотрен бинарный поиск. Перед поиском массив должен быть отсортирован. Сложность алгоритма бинарного поиска в среднем и в худшем случае составляет O(log n). Дополнительных алгоритмов не предусмотрено.

Collections.sort

В Collections сортировка предусмотрена только для списков. Интересно, что сначала производится преобразование списка в массив с последующим применением сортировки слиянием для массивов ссылочных типов. Сортировка осуществляется вызовом метода Arrays.sort.

Collections.binarySearch

Как и в случае с сортировкой, в Collections бинарный поиск реализован только для списков. Переменная BINARYSEARCH_THRESHOLD устанавливает ограничение на размер списка в 5000 элементов. Так что если вам необходимо провести поиск на более внушительной выборке, придется подумать, как это лучше сделать.

Списки поддерживают либо произвольный доступ, либо последовательный. Если список поддерживает произвольный доступ, то он будет обрабатываться алгоритмом индексированного бинарного поиска. Если список поддерживает последовательный доступ, то он будет обрабатываться алгоритмом итеративного бинарного поиска. Как видно, и в том, и в другом случае будет применяться бинарный поиск.

Всего интерфейс List в JDK 7.8 реализуют 10 классов, 2 из которых — абстрактные AbstractList и AbstractSequentialList. Последовательный доступ реализует только LinkedList и все потомки AbstractSequentialList. Поэтому они будут обрабатываться алгоритмом iteratorBinarySearch. Остальные списки, такие как ArrayList, CopyOnWriteArrayList, будут обрабатываться алгоритмом indexedBinarySearch.

UPD. Как стало понятно из личной дискуссии с Zamyslov, необходимо уточнить, каким образом BINARYSEARCH_THRESHOLD участвует в определении типа алгоритма сортировки. Это пороговое значение имеет влияние только на списки с последовательным доступом.

Cписок, поддерживающий произвольный доступ, будет всегда обрабатываться Collections.indexedBinarySearch. А список, поддерживающий последовательный доступ, будет обрабатываться Collections.iteratorBinarySearch только если он будет превышать значение BINARYSEARCH_THRESHOLD (см. листинг 3), в противном случае он также будет обрабатываться Collections.indexedBinarySearch.

Листинг 3. Влияние типов списков и константы BINARYSEARCH_THRESHOLD на определение алгоритмов обработки списка

Обобщаем изученное

Теперь, когда рассмотрены основные методы и условия перехода к дополнительным методам, можно обобщить полученные данные. Для максимальной наглядности детализируем рисунок 1, выделив на нем основные методы и добавим условия перехода к дополнительным методам.

Рисунок 2. Основные и дополнительные алгоритмы Arrays, Collections

Пояснения к цифрам на стрелках рисунка 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 .