Содержание:
1. Основные особенности алгоритмов
2. Описание алгоритма бинарного поиска
3. Алгоритм бинарного поиска на встроенном языке 1С
Написание собственных алгоритмов и понимание их работы – один из важнейших навыков, который должен быть у любого программиста. Хороший навык построения алгоритмов позволит программисту быстро решать любые задачи и сделает его гораздо эффективнее. За последние 30 лет произошёл очень сильный скачок в развитии технологий и за это время было написано большое количество различных алгоритмов. Но для начинающего программиста может быть достаточно сложно вникнуть в работу большого и комплексного алгоритма. Цель данной статьи, взять один из самых популярных алгоритмов и разобрать каждую его строчку. Но прежде чем переходить к алгоритму бинарного поиска, следует разъяснить что такое алгоритмы.
1. Основные особенности алгоритмов
Алгоритм – набор инструкций для выполнения некоторой задачи и получения какого-то результата в итоге. С алгоритмами можно встретится во всех сферах жизни. Например, разберём какие действия нужно сделать, чтобы включить компьютер:
1. Подойти к столу с компьютером;
2. Сесть на стул;
3. Подвинутся к столу;
4. Нажать на кнопку включения компьютера;
5. Если компьютер не подключён к электричеству, вставляем провод от блока питания в розетку;
6. Ещё раз нажимаем на кнопку включения компьютера.
Список, который описан выше и есть алгоритм. При помощи этих действий можно получить конечный результат в виде того, что компьютер включится. Конечно, то, как описан этот алгоритм, не соответствует реальности, так как в реальности алгоритм нужно прописать гораздо детальнее и продумать все сценарии, которые могут возникнуть при его работе. Теперь, после того как читатель знает что такое алгоритм, можно переходить к главной теме этой статьи.
2. Описание алгоритма бинарного поиска
Как можно понять из названия, алгоритм бинарного поиска используется при поиске какого-то значения. Предположим, что нужно в массиве, который заполнен числами от 0 до 100 вам нужно получить число 64. Конечно можно пройтись по каждому числу от 0 до 99, но для этого потребуется 99 шагов. Может показаться что это не очень много, но тогда можно привести ситуацию в которой массив заполнен до миллионов или сотен миллионов чисел и вам нужно получить какое-то число из середины этого массива. В такой ситуации проходить по каждому числу уже не кажется такой хорошей идеей. Именно для таких ситуаций и существует алгоритм бинарного поиска.
Бинарный поиск – алгоритм, который на входе получает отсортированный список элементов (например массив). Если элемент который нужно найти, есть в списке, бинарный поиск вернёт позицию(индекс элемента если говорить о массивах), в которой он был найден. Иначе бинарный поиск вернёт нам сообщение о том, что этого элемента нет в массиве.
В отличие от прохождения каждый раз по всем элементам массива заполненного числами от 0 до 100, с бинарным поиском мы каждый раз загадываем число в середине диапазона (то есть во время первой итерации мы получим число 50, так изначально диапазон поиска от 0 до 100) и исключаем половину оставшихся чисел.
Пример работы бинарного поиска
3. Алгоритм бинарного поиска на встроенном языке 1С
Сейчас будет приведён и подробно разобран алгоритм бинарного поиска, написанный на встроенном языке 1С:Предприятие. Входные данные будут: массив который заполнен числами от 0 до 100 и загаданное число: 43
Функция БинарныйПоиск(Массив, ЗагаданноеЧисло)
Меньшее = 0;
Большее = Массив.Количество()-1;
Пока Меньшее <= Большее Цикл
Среднее = (Меньшее + Большее) / 2;
ПредположительноеЧисло = Массив[Среднее];
Если ПредположительноеЧисло = ЗагаданноеЧисло Тогда
Возврат Среднее;
ИначеЕсли ПредположительноеЧисло > ЗагаданноеЧисло Тогда
Большее = Среднее - 1;
Иначе
Меньшее = Среднее + 1;
КонецЕсли;
КонецЦикла;
Сообщение = Новый СообщениеПользователю;
Сообщение.Текст = "Число:" + ЗагаданноеЧисло + " " + "нет в списке";
Сообщение.Сообщить();
КонецФункции
Листинг алгоритма бинарного поиска на языке 1С
Давайте разберём каждую строку которая есть.
«Меньшее = 0» - эта строка используется для обозначения границ списка который будет передаваться в наш алгоритм. При первой итерации эта переменная будет равна первому элементу списка (в данном случае 0)
«Большее = Массив.Количество()-1» - эта строка также используется для обозначения списка, но она используется для обозначения последнего элемента списка (в данном случае это 100)
«Пока Меньшее <= Большее Цикл» - эта строка используется для того, чтобы алгоритм работал, пока не останется один элемент списка.
«Среднее = (Меньшее + Большее) / 2» - эта строка используется для того, чтобы найти средний элемент списка. Например если передаётся список в котором 100 элементов, средний элемент будет 50.
«ПредположительноеЧисло = Массив[Среднее]» - при помощи этой строки, алгоритм создаёт предположительное число, при помощи которого, он будет искать число, которое было загадано.
«Если ПредположительноеЧисло = ЗагаданноеЧисло Тогда
Возврат Среднее» - с этой строки начинается условие, которое будет искать загаданное число. В этом случае, если предположительное число равно числу которое мы загадали, система вернёт его.
«ИначеЕсли ПредположительноеЧисло > ЗагаданноеЧисло Тогда
Большее = Среднее – 1» - строка с этим условием, подразумевает, что если предположительное число будет больше чем загаданное число, переменная которая хранит в себе наибольший элемент, станет хранить Среднее число массива – 1. То есть в первой итерации, система перейдёт по этому условию, среднее число будет 50 и в итоге получается, что переменная «Больше» будет хранить в себе 49. Таким образом мы сокращаем интервал поиска загаданного числа.
«Иначе
Меньшее = Среднее + 1» - эта строка будет отрабатывать в случае, если предположительное число меньше загаданного числа. Смысл этой строки в том, что если предположительное число меньше загаданного, переменная «Меньше», которая хранит в себе первый элемент списка, после этой строки станет хранить значение среднего числа списка + 1. Это делается для того, чтобы сузить интервал в котором происходит поиск числа. То есть во второй итерации (в случае когда на вход даётся список заполненный элементами от 0 до 100), система перейдёт по этому условию. Среднее число будет 24( Меньшее = 0, Большее = 49 (0+49)/2 = 24,5). В итоге получается, что теперь система будет искать загаданное число в диапазоне между 24 и 49.
«Сообщение = Новый СообщениеПользователю
Сообщение.Текст = "Число:" + ЗагаданноеЧисло + " " + "нет в списке"
Сообщение.Сообщить()» - эти строки используются в том случае, если переменная «Меньшее» становится больше переменной «Большее» и мы выходим из цикла «Пока». Строки эти нужны для того, чтобы уведомить пользователя, что в передаваемом списке нет элемента который он ищет.
Подводя итоги, можно сказать, что была разобрана каждая строка алгоритма бинарного поиска. Теперь у начинающего программиста есть понимание его работы, но теории недостаточно и автор настоятельно рекомендует повторить этот пример у себя и посмотреть в отладчике, как будет работать этот алгоритм. Если у читателя возникнет желание подробнее разобраться в алгоритмах и изучить новые, тогда можно обратится к книге "Грокаем алгоритмы" за авторством Адитьи Бхаргавы. В этой книге доступно объясняется что такое О-большое, рекурсия и другие термины, которые нужно знать программисту чтобы разбираться в алгоритмах.
Специалист компании "Кодерлайн"
Егор Винников
