"Информатика (в 2-х частях)", Горячев А.В., Герасимова В.Г., Макарина Л.А., Островский С.Л., Паволоцкий А.В., Семёнов А.А., Юдина А.Г., Чернышёва Т.Л.
Упорядоченный массив хранит значения по возрастанию или убыванию, поэтому его элементы расположены не случайно. Такая организация помогает быстрее находить нужное значение: при бинарном поиске на каждом шаге можно отбросить часть массива. Но при вставке нового элемента порядок приходится сохранять — для этого определяют место вставки и сдвигают часть значений. В теме разбираются проверка порядка, два способа поиска и вставка.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Упорядоченный массив — массив, элементы которого расположены по возрастанию или убыванию. Порядок должен соблюдаться у каждой пары соседей: при возрастании следующий элемент не меньше предыдущего, а при убывании — не больше. Например, числа 2, 5, 5, 9 образуют упорядоченный массив. Такое расположение позволяет использовать специальные способы поиска.
Линейный поиск — последовательная проверка элементов массива, пока не найдено нужное значение или не проверены все элементы. Сравнение начинают с первого элемента и переходят к следующему, если совпадения нет. Этот способ подходит даже для массива без порядка. Он нужен, когда нельзя заранее отбрасывать часть данных.
Бинарный поиск — поиск в упорядоченном массиве, при котором область возможного нахождения значения на каждом шаге сокращается примерно вдвое. Для этого сравнивают искомое значение со значением в середине текущего участка. Затем оставляют только ту половину, где искомое ещё может находиться. Такой способ полезен, когда элементов много.
Вставка в упорядоченный массив — добавление нового значения на подходящее место с сохранением общего порядка. Если место не в конце, элементы справа сначала сдвигают на одну позицию, иначе новое значение может затереть прежнее. Затем освободившуюся ячейку занимают новым элементом. Это позволяет и дальше пользоваться быстрым поиском.
Чтобы проверить, упорядочен ли массив, сравнивают каждую пару соседних элементов. Для порядка по возрастанию проверяют, что следующий элемент не меньше предыдущего; если хотя бы одна пара этому правилу не соответствует, весь массив не упорядочен по возрастанию. Для убывания условие обратное: следующий элемент не больше предыдущего. Проверка соседей достаточна, потому что цепочка таких сравнений задаёт порядок всего массива.
Бинарный поиск возможен благодаря тому, что значения уже расположены по порядку. Допустим, массив растёт, а искомое число больше значения в середине. Тогда все элементы левее середины тоже меньше искомого, и проверять их незачем. Если искомое меньше значения середины, исключают правую часть. В неупорядоченном массиве такого вывода сделать нельзя: по одному элементу в середине невозможно определить, где искать дальше.
Сначала для бинарного поиска задают границы участка, например индексами его первого и последнего элементов. Находят середину текущего участка и сравнивают её значение с искомым. Если значения равны, поиск завершён; если нет, оставляют подходящую половину, не включая уже проверенную середину. Эти действия повторяют, пока значение не найдётся или левая граница не окажется правее правой. Во втором случае участок пуст, значит, искомого элемента в массиве нет.
Чтобы вставить число в массив по возрастанию, сначала находят первое место, где стоящее значение больше нового, либо выбирают конец, если все значения меньше или равны ему. Затем начинают сдвиг справа налево: каждый элемент перемещают на одну позицию вправо. Такой порядок сдвига важен, потому что при движении слева направо данные можно перезаписать до того, как они будут сохранены. После сдвига новое число записывают в освободившуюся ячейку.
Упорядоченность помогает экономить проверки при поиске: бинарный алгоритм не просматривает значения по одному, а сразу исключает целые участки. Но массив не становится удобнее во всём: при вставке в середину нужно перемещать расположенные справа элементы. Чем дальше от конца находится место вставки, тем больше значений придётся сдвинуть. Поэтому способ организации данных выбирают с учётом того, что чаще делают: ищут или добавляют элементы.
| Операция | Как выполняется | Требование к массиву | Что происходит с элементами |
|---|---|---|---|
| Линейный поиск | Проверяют элементы по очереди, пока не найдут совпадение или не закончатся значения. | Порядок не требуется. | Элементы только сравнивают, их расположение не меняется. |
| Бинарный поиск | Сравнивают искомое значение с серединой участка и оставляют подходящую половину. | Массив должен быть упорядочен. | Элементы сравнивают, а границы участка поиска сужают. |
| Вставка нового элемента | Находят место, сдвигают элементы справа и записывают новое значение. | Чтобы сохранить порядок, массив должен быть упорядочен. | Часть элементов перемещают на одну позицию вправо. |
Сравни таблицу по двум вопросам: нужен ли для операции упорядоченный массив и меняются ли сами элементы. Для поиска выбирай линейный способ, если порядок не гарантирован, а бинарный — если он соблюдён. При вставке учитывай, что порядок придётся поддерживать перемещением значений.
Задача 1. В массиве [2, 5, 8, 11, 14] нужно найти значение 8 линейным поиском и указать число проверенных элементов. Идём от начала, не пытаясь пропускать элементы: линейный поиск проверяет их последовательно. После каждого сравнения решаем, продолжать ли просмотр. Когда значение найдено, дальнейшие проверки не нужны.
Ответ: число 8 находится на третьей позиции массива; проверено 3 элемента. Здесь позиции считаются с единицы, а если в программе используются индексы с нуля, индекс найденного элемента равен 2.
Задача 2. В массиве [3, 7, 10, 15, 21, 28, 34] нужно найти 21 бинарным поиском и записать проверяемые середины. Массив упорядочен по возрастанию, значит, сравнение с серединой позволяет выбрать нужную половину. При нечётном числе элементов берём средний элемент текущего участка. Проверенную середину повторно не включаем в следующий участок.
Ответ: проверяемые середины — 15, 28, 21; значение найдено. На каждом шаге исключали часть массива, где числа 21 быть не могло, поэтому не пришлось проверять все семь элементов.
Задача 3. В массив [4, 9, 13, 18, 25] нужно вставить 16 так, чтобы порядок сохранился, и показать массив после сдвига. Ищем место, где новое число должно стоять: оно больше 13, но меньше 18. Значит, элементы 18 и 25 нужно передвинуть вправо, начиная с правого края, чтобы сохранить их значения.
Ответ: после сдвига и вставки получаем [4, 9, 13, 16, 18, 25]. Последовательность по возрастанию сохранена. Если массива фиксированного размера недостаточно для нового значения, программе понадобится дополнительная ячейка или другой способ хранения.
Применять бинарный поиск к неупорядоченному массиву. Ошибка возникает, если помнить о быстром поиске, но забыть, что половину можно отбросить только при известном порядке значений. Тогда сравнение с серединой не показывает, где находится искомое. Перед началом проверь соседние элементы или используй линейный поиск.
Оставлять проверенную середину в следующем участке. Так делают, когда обновляют только одну границу и не исключают уже просмотренный элемент. В результате середина может проверяться повторно, а алгоритм иногда зацикливается. После сравнения с серединой сдвигай границу за неё: например, при поиске справа начинай участок с mid + 1.
Перепутать границы участка поиска. Если после очередного шага обратиться к индексу за пределами массива, программа может выдать ошибку или прочитать неверное значение. Такое случается при неверном обновлении левой и правой границ. Перед вычислением середины проверяй, что левая граница не больше правой: иначе участок уже пуст.
Записать новое значение до сдвига. При вставке в середину массива такая запись может затереть элемент, который ещё не перемещён. Обычно ошибку допускают, если начинают сдвиг слева направо и не учитывают, что значения перезаписываются. Сначала двигай элементы от конца к месту вставки, затем записывай новое значение и проверь соседей вокруг него.
Для работы с массивами нужно уметь задавать массив, обращаться к элементу по индексу и сравнивать значения. Без этих действий нельзя проверить соседей, определить середину участка или переместить элемент. Поиск и вставка опираются на циклы, которые повторяют шаги, и ветвления, которые выбирают дальнейшее действие по результату сравнения. Позже упорядоченные массивы и бинарный поиск пригодятся при изучении алгоритмов поиска и обработки больших наборов данных.
Обязательно ли массив должен быть упорядочен по возрастанию?
Нет, порядок может быть и убывающим. Главное, чтобы все соседние элементы подчинялись одному правилу: каждый следующий не меньше предыдущего или каждый следующий не больше предыдущего.
Почему бинарный поиск работает быстрее линейного?
Линейный поиск проверяет элементы по одному, а бинарный после сравнения с серединой исключает примерно половину оставшихся значений. Поэтому на большом упорядоченном массиве обычно требуется гораздо меньше сравнений.
Можно ли применять бинарный поиск, если в массиве есть одинаковые значения?
Да, одинаковые значения не мешают бинарному поиску, если массив по-прежнему упорядочен. Поиск может найти одно из вхождений; чтобы найти первое или последнее, нужно дополнительно продолжить проверку в подходящей части массива.
Что делать, если искомого значения в массиве нет?
В линейном поиске нужно проверить все элементы и сообщить, что совпадения нет. В бинарном поиске отсутствие значения устанавливают, когда текущий участок поиска опустел.
Почему при вставке в упорядоченный массив приходится сдвигать элементы?
Новое значение должно оказаться между подходящими соседями, а не просто в конце массива. Поэтому элементы, которые стоят правее места вставки, временно перемещают на одну позицию вправо, освобождая ячейку.
§ 8. Работа с упорядоченными массивами
