Приветствую всех читателей публикации! Я являюсь автором телеграмм канала "Заметки джависта", а совсем недавно начал погружение в алгоритмы. Сейчас читаю книгу "Грокаем алгоритмы", и планирую объяснять изученный материал простыми словами.

В этой статье мы разберемся с тем, как работают массивы, что такое алгоритмы, и как устроен бинарный поиск "под капотом". Погнали!

Алгоритмы в программировании

Алгоритмом называется последовательность действий, приводящих к результату. Целью алгоритма может быть что угодно: отсортировать список элементов по конкретному параметру, найти минимальное или максимальное число и т.д.

Пример: для приготовления супа нужно совершить ряд последовательных действий: приготовить ингредиенты, отварить мясо, добавить картошку, обжаренные овощи, посолить и закрыть крышкой для настаивания.

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

Что такое массив?

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

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

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

В данном примере мы рассматриваем место под номером 1, в 1 ряду - для простоты обозначим это место как 1х1.

Память в приложении можно также представить в виде кинозала - это такое большое, организованное место, в котором есть места. Каждое такое место называется ячейкой (ячейка памяти), и каждая ячейка, как и место в кинозале, имеет свой адрес (в нашем примере это 1х1). Таким образом все ячейки имеют свой адрес и какой-то порядок.

Также надо понимать, что память, как и кинозал, имеет свой лимит - в каждом кинозале есть определенное количество сидений, также как и в памяти есть определенное количество этих самых мест (ячеек памяти).

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

Теперь представим, что ваша компания друзей из 5 человек пошла в кинотеатр. Логично, что вы захотите сесть все вместе, рядом друг с другом - в таком случае вы купите 5 билетов. Вы долго думали, и решили сесть в самом центре, поэтому взяли 5 билетов в 7 ряду:

Ячейки, помеченные серым - занятые места. Ровно также, как и занятые ячейки в памяти.

Первое место занял друг Ваня, под номером 9 ряда 7 - для простоты обозначим как 9x7. Последней среди друзей была Аня - она купила билет на место 13 ряда 7 - (обозначим как 13x7).

В сумме мы заняли 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]);

За основу я взял тот же пример, что и ранее: добавился лишь вывод первого элемента. Теперь на консоль будет выведено значение "9x7", так как мы обратились к первому элементу массива, с ячейкой под номером 0 (как мы уже помним, нумерация элементов в массиве начинается с 0).

С массивами разобрались - теперь можно приступать к бинарному поиску!

Бинарный поиск

Как уже понятно из названия, речь пройдет про поиск. Мы встречаем его везде: при поиске запроса в поисковой строке Google, или при поиске своих вещей, номеров в записной книжке.

Что же представляет собой бинарный поиск?

Бинарный поиск - поиск элемента упорядоченного множества путем деления этого множества пополам.

А теперь простыми словами: упорядоченный (отсортированный) список значений делится каждый раз на 2, до тех пор, пока мы не найдем нужный элемент.

И самое главное: бинарный поиск работает только для отсортированных массивов!

Теперь абстрагируемся и рассмотрим новый пример:

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

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

Допустим, фамилия нужного нам контакта - "Алексеев". В данном случае мы отсекаем большую часть словаря, так как фамилия начинается на первую букву алфавита. Далее, мы смотрим вторую букву фамилии - "л", соответственно отбрасываем все фамилии, следующие после или перед "Ал", и таким образом доходим до нужного нам контакта. В данном подходе мы не смотрим все контакты записной книги, а последовательно отбрасываем часть контактов, что в итоге значительно упрощает и ускоряет процесс поиска.

Таким же образом мы можем представить угадывание числа в массиве значений диапазона от 0 до 100. Мы можем найти нужное число делением на 2 за каждый шаг (итерацию).

Представим, что загаданное число - 65. Тот, кто загадал число, будет говорить, является ли наше число загаданным, большим либо меньшим загаданного. Порядок действий будет следующим:

• Переходим в середину массива, это число 50. Сравниваем число 50 с загаданным 65 - число 50 меньше, а значит мы идем дальше, вправо. Итак, мы отсекли уже первые 50 чисел! Таким образом, мы сократили количество итераций вдвое!

• Смотрим дальше: наш диапазон сузился, и составляет числа от 51 до 100. Серединой этого диапазона = (51 + 100) / 2 = 75. Число 75 больше, чем загаданное? - Да. Значит мы отсекаем часть чисел после 75. Этим действием мы убрали еще 25 чисел, которые попросту нет смысла смотреть - мы уже знаем, что они не подходят!

• Это деление проходит до тех пор, пока наш список чисел не сузится до тех пор, пока мы не упремся в ситуацию, когда средний элемент массива равен загаданному числу, либо до тех пор, пока диапазон не сузится до 1 элемента. Число найдено, можно ликовать!

Описанные выше действия и составляют всю логику бинарного поиска. Таким же образом работает поиск среди других форматов данных, например строк! Если нам нужно найти нужную строку в массиве строк, либо нужный контакт по фамилии человека, мы попросту отсекаем половину списка на каждой итерации. Такой подход позволяет находить нужный элемент в массиве за операций - что означает обратное возведение в квадрат. Т.е логарифм является обратной операцией возведения в степень:

Реализация бинарного поиска на Java

Изначально я писал бинарный поиск самостоятельно, поняв лишь саму идею. На это у меня ушло около 2 часов, так как я постоянно тупил и допускал ошибки в реализации.

Условия задачи на leetcode:

Дан массив целых чисел nums, отсортированный по возрастанию, и целочисленный искомый элемент. Напишите функцию для поиска искомого в nums. Если искомое существует, необходимо вернуть ее индекс. В противном случае вернуть -1.

Необходимо написать алгоритм со сложностью выполнения O(log n).

Сейчас мы пошагово рассмотрим, как я мыслил, какие ошибки допускал, и как прийти к верному решению:

1. Цикл. Очевидно, что деление массива неоднократно повторяющееся действие. Значит, нам нужен цикл, по которому мы будем проходить (итерироваться), и в зависимости от условий убирать левую или правую части массива.

2. Хранение границ элемента в переменных. Для того, чтобы работать с границами (левую и правую части) массива, необходимо создать для них переменные, а также хранить индекс среднего элемента.

3. Негативный сценарий. Может быть случай, при котором искомый элемент отсутствует в массиве чисел. В таком случае нужно возвращать не индекс элемента, а -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, и так бесконечно. Середина массива всегда получается одна и та же. Как это фиксить? Попробуйте подумать сами, а решение будет ждать вас в спойлере.

В коде это выглядит так:

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:

Аналогичная ситуация происходит, когда элемент под индексом mid (середина диапазона) БОЛЬШЕ, чем искомое значение - значит искомый элемент меньше элемента в середине, и нам нужно откинуть правую часть включая средний элемент - для этого мы откидываем все элементы после mid, включая сам mid. Происходит операция, похожая предыдущей - только наоборот, 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;
    }
}

Искренне надеюсь, что смог объяснить вещи простыми словами. Если вы дошли до этого момента - вы большой молодец!

Продолжайте изучение алгоритмов и следите за новыми публикациями!