Бинарный поиск на пальцах
Приветствую всех читателей публикации! Я являюсь автором телеграмм канала «Заметки джависта», а совсем недавно начал погружение в алгоритмы. Сейчас читаю книгу «Грокаем алгоритмы», и планирую объяснять изученный материал простыми словами.
В этой статье мы разберемся с тем, как работают массивы, что такое алгоритмы, и как устроен бинарный поиск «под капотом». Погнали!
Алгоритмы в программировании
Алгоритмом называется последовательность действий, приводящих к результату. Целью алгоритма может быть что угодно: отсортировать список элементов по конкретному параметру, найти минимальное или максимальное число и т.д.
Пример: для приготовления супа нужно совершить ряд последовательных действий: приготовить ингредиенты, отварить мясо, добавить картошку, обжаренные овощи, посолить и закрыть крышкой для настаивания.
Такой же набор действий существует и в программировании: в зависимости от задачи мы выполняем вполне конкретный набор действий в указанном порядке, которые в конечном итоге приводят к нужному результату (будь то сортировка списка элементов/нахождение минимального или максимального элемента).
Что такое массив?
Для более детального погружения в алгоритмы нужно понимать, как устроены структуры данных в программировании.
Текущая тема предполагает, что вы уже знакомы со структурой данных «массив» изнутри. Для тех, кто не знаком с массивами или не уверен, что полностью понимают их принцип работы в деталях, я подготовил вполне простое объяснение на примерах с иллюстрациями:
Понятнее будет на примере кинотеатра. Представьте, что вы покупаете билет в кинотеатр — заходите на сайт, и видите доступные для покупки места:
Схема мест в кинотеатре
В данном примере мы рассматриваем место под номером 1, в 1 ряду — для простоты обозначим это место как 1×1.
Память в приложении можно также представить в виде кинозала — это такое большое, организованное место, в котором есть места. Каждое такое место называется ячейкой (ячейка памяти), и каждая ячейка, как и место в кинозале, имеет свой адрес (в нашем примере это 1×1). Таким образом все ячейки имеют свой адрес и какой-то порядок.
Также надо понимать, что память, как и кинозал, имеет свой лимит — в каждом кинозале есть определенное количество сидений, также как и в памяти есть определенное количество этих самых мест (ячеек памяти).
Какие-то ячейки памяти могут быть уже заняты какими-либо значениями, которые вписывают другие программы или компоненты. Собственно также, как и места в кинотеатре: по приходу в кинозал вы можете оказаться в ситуации, когда свободных мест вообще нет.
Теперь представим, что ваша компания друзей из 5 человек пошла в кинотеатр. Логично, что вы захотите сесть все вместе, рядом друг с другом — в таком случае вы купите 5 билетов. Вы долго думали, и решили сесть в самом центре, поэтому взяли 5 билетов в 7 ряду:
Схема покупки мест в кинотеатре
Ячейки, помеченные серым — занятые места. Ровно также, как и занятые ячейки в памяти.
Первое место занял друг Ваня, под номером 9 ряда 7 — для простоты обозначим как 9×7. Последней среди друзей была Аня — она купила билет на место 13 ряда 7 — (обозначим как 13×7).
В сумме мы заняли 5 мест в 7 ряду, с 9 по 13 место включительно. Также устроены и массивы: при создании этой структуры данных, мы резервируем n последовательных ячеек памяти (в нашем примере — количество сидений), где n — любое неотрицательное целое число (в нашем случае это 5, так как мы купили 5 мест).
Для примера создадим массив строк в Java, в котором будут храниться номера билетов для всех членов компании:
String[] ticketsArray = new String[]{"9x7", "10x7", "11x7", "12x7", "13x7"};
В некоторых кинотеатрах есть возможность бронирования мест — вы можете обозначить, что эти места принадлежат вам, но билеты еще не оплачены. Вы можете оплатить их чуть позже, но они уже «привязаны» к вам.
Также и в памяти: мы можем зарезервировать определенное количество ячеек под наши нужды. В нашем примере мы резервируем 5 ячеек под массив, который хранит номера билетов в кинозале.
Собственно сейчас мы вплотную подобрались к тому, что представляют собой массивы:
Массив — структура данных, хранящая набор значений определенного типа (в массив нельзя класть данные разных типов — если массив обьявлен как String[], то и значения там могут быть только типа String).
Ключевым является понимание механизма резервации, благодаря чему мы и имеем возможность создавать массив, а также получаем те «плюшки», которые дает нам эта структура данных.
Это означает, что при создании массива происходит резервация близлежащих ячеек, как и мест в кинотеатре для компании друзей в последнем примере. Нельзя зарезервировать под массив 3 места, которые находятся в разных частях памяти. Такие ограничения позволяют пользоваться преимуществом массивов — доступ к элементу по индексу за константное время.
Создать массив размерности n = 15, зарезервировав тем самым память под этот массив (при этом не обязательно заполнять его значениями сразу) можно следующим способом:
String[] ticketsArray = new String[15];
В данном случае мы лишь «резервируем» ячейки в памяти — как и билеты в кинозале. Возможно наш массив размера 15 будет иметь всего лишь 1 значение -, но его вместимость составляет по-прежнему 15 элементов, и выделенная под него память никуда не исчезнет. (Это как арендовать 15 столов для гостей на свадьбе. Не факт, что придут все гости, и по итогу некоторые столы окажутся пустыми. Но это по-прежнему 15 столов, которые зарезервированы под вашу свадьбу :))
Еще несколько важных слов про массивы, прежде чем мы перейдем далее:
Массив имеет индексы. Это указатели, которые позволяют обращаться к конкретному элементу массива.
Индексы внутри массива начинаются с 0. При создании массива размера 5, первый элемент находится под номером 0, тогда как последний под номером 4. (Когда я впервые об этом узнал, мой мозг взрывался в попытках понять происходящее, но поверьте, вы скоро к этому привыкнете)
Размер массива нельзя увеличить. С тех пор как выделяемое место статично, мы выделяем место под массив на этапе объявления. Чтобы увеличить размер, необходимо создать новый массив и перенести туда данные со старого массива.
Для понимания можно представить листик в клетку, на котором находится 32 клетки в длину. Вырезав линию из 20 клеток, мы не можем добавить туда еще. Для этого нам нужно вырезать новую линию, с большим количеством клеток. Также и с массивами — выделив однажды место под массив, можно пользоваться этим диапазоном ячеек. Чтобы добавить еще, необходимо создать новый массив с большим размером.
Благодаря тому, что выделяемое под массив место является непрерывным блоком данных в памяти, получение элемента массива по индексу происходит за константное время — O (1) (то есть всегда за одинаковое время).
Представьте, что вы живете в 12 квартире. Вам нужно узнать, под каким номером находится квартира вашего соседа. Логично, что номер квартиры соседа — 13. Также работают и массивы: зная ячейку начала массива, мы можем обратиться к нужному индексу массива за фиксированное (константное) время. Такое вычисление производит сам массив при обращении к нужному элементу. Разработчику следует лишь указать номер нужного индекса!
Для лучшего понимания последнего пункта, приведу более подробное разъяснение:
При создании, массив хранит адрес начала. Если нам нужно получить третий элемент массива — мы просто обращаемся к элементу массива под индексом 2 (помним, что отсчет идет с 0), и «под капотом» происходит подсчет адреса ячейки, в которой лежит нужное нам значение.Зная адрес начала массива, мы просто обращаемся к этому адресу + 2, и получаем нужный элемент. Мы обращаемся туда, забираем значение, и готово!
Итак, чтобы обратиться к конкретному элементу массива, мы просто обращаемся по индексу:
String[] ticketsArray = new String[]{"9x7", "10x7", "11x7", "12x7", "13x7"};
System.out.println(ticketsArray[0]);За основу я взял тот же пример, что и ранее: добавился лишь вывод первого элемента. Теперь на консоль будет выведено значение »9×7», так как мы обратились к первому элементу массива, с ячейкой под номером 0 (как мы уже помним, нумерация элементов в массиве начинается с 0).
С массивами разобрались — теперь можно приступать к бинарному поиску!
Бинарный поиск
Как уже понятно из названия, речь пройдет про поиск. Мы встречаем его везде: при поиске запроса в поисковой строке Google, или при поиске своих вещей, номеров в записной книжке.
Что же представляет собой бинарный поиск?
Бинарный поиск — поиск элемента упорядоченного множества путем деления этого множества пополам.
А теперь простыми словами: упорядоченный (отсортированный) список значений делится каждый раз на 2, до тех пор, пока мы не найдем нужный элемент.
И самое главное: бинарный поиск работает только для отсортированных массивов!
Теперь абстрагируемся и рассмотрим новый пример:
Представим, что нам нужно найти номер человека в записной книге. Зная его фамилию, мы можем найти его контакты за очень быстрое время.
Когда мы ищем слово в словаре, или контакт в записной книге, мы не просматриваем все записи, а начинаем сразу с нужной буквы. Таким образом, мы отсекаем большую часть книги, просматривать которую нет смысла.
Допустим, фамилия нужного нам контакта — «Алексеев». В данном случае мы отсекаем большую часть словаря, так как фамилия начинается на первую букву алфавита. Далее, мы смотрим вторую букву фамилии — «л», соответственно отбрасываем все фамилии, следующие после или перед «Ал», и таким образом доходим до нужного нам контакта. В данном подходе мы не смотрим все контакты записной книги, а последовательно отбрасываем часть контактов, что в итоге значительно упрощает и ускоряет процесс поиска.
Таким же образом мы можем представить угадывание числа в массиве значений диапазона от 0 до 100. Мы можем найти нужное число делением на 2 за каждый шаг (итерацию).
Представим, что загаданное число — 65. Тот, кто загадал число, будет говорить, является ли наше число загаданным, большим либо меньшим загаданного. Порядок действий будет следующим:
Переходим в середину массива, это число 50. Сравниваем число 50 с загаданным 65 — число 50 меньше, а значит мы идем дальше, вправо. Итак, мы отсекли уже первые 50 чисел! Таким образом, мы сократили количество итераций вдвое!
Смотрим дальше: наш диапазон сузился, и составляет числа от 51 до 100. Серединой этого диапазона = (51 + 100) / 2 = 75. Число 75 больше, чем загаданное? — Да. Значит мы отсекаем часть чисел после 75. Этим действием мы убрали еще 25 чисел, которые попросту нет смысла смотреть — мы уже знаем, что они не подходят!
Это деление проходит до тех пор, пока наш список чисел не сузится до тех пор, пока мы не упремся в ситуацию, когда средний элемент массива равен загаданному числу, либо до тех пор, пока диапазон не сузится до 1 элемента. Число найдено, можно ликовать!
Массив чисел от 0 до 100
Описанные выше действия и составляют всю логику бинарного поиска. Таким же образом работает поиск среди других форматов данных, например строк! Если нам нужно найти нужную строку в массиве строк, либо нужный контакт по фамилии человека, мы попросту отсекаем половину списка на каждой итерации. Такой подход позволяет находить нужный элемент в массиве за 
операций — что означает обратное возведение в квадрат. Т.е логарифм является обратной операцией возведения в степень:
Объяснение логарифма (Грокаем алгоритмы, Бхаргава А.)
Реализация бинарного поиска на Java
Изначально я писал бинарный поиск самостоятельно, поняв лишь саму идею. На это у меня ушло около 2 часов, так как я постоянно тупил и допускал ошибки в реализации.
Условия задачи на leetcode:
Дан массив целых чисел nums, отсортированный по возрастанию, и целочисленный искомый элемент. Напишите функцию для поиска искомого в nums. Если искомое существует, необходимо вернуть ее индекс. В противном случае вернуть -1.
Необходимо написать алгоритм со сложностью выполнения O (log n).
Сейчас мы пошагово рассмотрим, как я мыслил, какие ошибки допускал, и как прийти к верному решению:
Цикл. Очевидно, что деление массива неоднократно повторяющееся действие. Значит, нам нужен цикл, по которому мы будем проходить (итерироваться), и в зависимости от условий убирать левую или правую части массива.
Хранение границ элемента в переменных. Для того, чтобы работать с границами (левую и правую части) массива, необходимо создать для них переменные, а также хранить индекс среднего элемента.
Негативный сценарий. Может быть случай, при котором искомый элемент отсутствует в массиве чисел. В таком случае нужно возвращать не индекс элемента, а -1. Следует ограничить цикл, и понять, что в какой-то момент мы прошлись по всему массиву, дошли до последнего элемента, но в случае, если он не равен числу которое мы ищем, вернуть -1.
Первое, что я сделал — верхнеуровнево накидал код, который выглядел примерно так:
public class Main {
public static void main(String[] args) {
int result = search(new int[]{1, 3, 5, 6, 9}, 99);
System.out.println(result);
}
public static int search(int[] nums, int target) {
int low = 0;
int high = nums.length - 1;
int mid = (low + high) / 2;
while (true) { // бесконечный цикл
if (target == nums[mid]) { // если искомое число равно среднему элемент массива, возвращаем индекс этого элемента
return mid;
}
if (target > nums[mid]) { // если искомое число больше, чем средний элемент массива, отбрасываем левую часть диапазона
low = mid;
mid = (low + high) / 2; // считаем новую середину массива, после того как отбросили левую часть
} else if (target < nums[mid]) { // иначе, если искомое число меньше, чем середина, отбрасываем правую часть диапазона
high = mid;
mid = (low + high) / 2; // считаем новую середину массива, после того как отбросили правую часть
} else { // иначе элемент не найден, возвращаем -1
return -1;
}
}
}
}Теперь рассмотрим первую итерацию по массиву:
Первая итерация моего шедевро-цикла
Как видно, наша цель — найти индекс элемента 99. Вот только 1 незадача: такого элемента здесь нет, и в таком случае массив должен вернуть -1. Запустим код, и получим. Бесконечный цикл, Карл!
Разберемся, почему так:
1) В условии while указан true, из-за чего в случае, когда нужного числа нет (в нашем примере числа 99 нет внутри массива чисел), цикл будет повторяться снова и снова.
2) Когда мы заходим во второе условие 15 строки, наш элемент 99 действительно больше середины. Далее должно происходить смещение — если отсекаем левую часть, то low должна равняться mid + 1, так как средний элемент, с которым мы сравнивали, оказался меньше, чем нужное нам число, соответственно надо перескочить этот средний элемент на 1 позицию вправо (mid + 1). На схеме это будет выглядеть так:
Правильная работа алгоритма
Но этого не происходит, в результате чего мы снова входим в цикл, получаем mid = 2, и так бесконечно. Середина массива всегда получается одна и та же. Как это фиксить? Попробуйте подумать сами, а решение будет ждать вас в спойлере.
Скрытый текст
Для того, чтобы корректно посчитать новые индексы нижней границы (low) и верхней границы (high), требуется смещать их на 1 элемент влево или вправо.
Также необходимо ввести ограничение при выполнении цикла. В случае, когда нижний и верхний диапазоны пересеклись (т.е произошла ситуация, когда мы прошлись по всему массиву и не нашли совпадений — low и high будут ссылаться на тот же индекс массива), требуется завершить цикл.
В коде это выглядит так:
public static int search(int[] nums, int target) {
int low = 0;
int high = nums.length - 1;
int mid = (low + high) / 2;
while (low <= high) { // итерируемся до тех пор, пока левая и правая часть не пересеклись
if (target == nums[mid]) {
return mid;
}
if (target > nums[mid]) {
low = mid + 1; // смещаем границу low вправо на 1 элемент
} else {
high = mid - 1; // смещаем границу high влево на 1 элемент
}
mid = (low + high) / 2; // пересчитываем середину массива после смещения диапазонов low, high
}
return -1; // искомое число не найдено
}Разберемся, что поменялось:
1) Мы исправили бесконечный цикл на условие low <= high, что буквально означает: мы итерируемся по массиву и ищем искомое число до тех пор, пока не окажется, что указатели (low/high) указывают на 1 элемент. В таком случае мы прошли весь массив и не нашли искомое число.
2) После выполнения цикла, мы возвращаем -1. Это сработает в случае, если за время выполнения цикла искомое значение не будет найдено. В противном случае, если искомое будет найдено, в строке 8 будет возвращена его позиция, и после команды return мы полностью выйдем из метода search (int[] nums, int target).
3) Внутри цикла мы поменяли последовательность (чтобы пересчитывать середину массива уже после изменений low и high границ), ведь надо считать середину массива уже после того, как мы отсекли часть элементов, и пересчитали low/high границы.
Разберемся с тем, как происходит изменение границ low и high чуть подробнее, чтобы все точно стало понятно:
В случае, когда значение в позиции mid (середина диапазона) меньше, чем искомое значение — мы переходим вправо. Т.е нам нужно откинуть левую часть, и нижняя граница (low) переместится в то место, где была середина, +1. Середину мы уже проверили на первом шаге, когда вошли в цикл — и выяснили, что искомое больше чем элемент в позиции mid, соотвественно надо пропустить mid, и перенести границу low в ячейку под индексом 3. Ровно поэтому мы и делаем low = mid + 1:
Смещение нижней границы low = mid + 1
Аналогичная ситуация происходит, когда элемент под индексом mid (середина диапазона) БОЛЬШЕ, чем искомое значение — значит искомый элемент меньше элемента в середине, и нам нужно откинуть правую часть включая средний элемент — для этого мы откидываем все элементы после mid, включая сам mid. Происходит операция, похожая предыдущей — только наоборот, high = mid — 1:
Смещение верхней границы high = mid — 1
После оптимизации и упрощения, итоговый вариант бинарного поиска выглядит следующим образом:
public class Main {
public static void main(String[] args) {
int result = search(new int[]{1, 3, 5, 6, 9}, 99);
System.out.println(result);
}
public static int search(int[] nums, int target) {
int low = 0;
int high = nums.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (target == nums[mid]) {
return mid;
}
if (target > nums[mid]) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
}Искренне надеюсь, что смог объяснить вещи простыми словами. Если вы дошли до этого момента — вы большой молодец!
Продолжайте изучение алгоритмов и следите за новыми публикациями!
