Алгоритмы — это интересно!

На канале уже выпущены две статьи про бинарный поиск и бинарные деревья. Но что же значит «Бинарный»? Давайте разберемся. «Бинарный» происходит от латинского binarius — «двойной». В информатике это означает «состоящий из двух частей» или «имеющий два варианта». Ключевые идеи: * два варианта: да/нет, 0/1, левое/правое; * выбор между двумя возможностями на каждом шаге. Бинарный поиск — алгоритм поиска элемента в отсортированном массиве, где на каждом шаге мы: 1. Смотрим на средний элемент массива. 2. Сравниваем его с искомым значением. 3. Отбрасываем половину массива (левую или правую) — в зависимости от результата сравнения. 4. Повторяем шаги 1–3 для оставшейся половины. Почему «бинарный»: на каждом шаге выбор сводится к двум вариантам: - искомое значение находится в левой половине; - искомое значение находится в правой половине. Бинарное дерево — структура данных, где каждый узел имеет: - не более двух потомков (левого и правого); - значение в узле; - ссылки на левого и правого потомка (или null, если потомка нет). Бинарное дерево поиска добавляет правило упорядоченности: * значения в левом поддереве < значения в корне; * значения в правом поддереве > значения в корне. Почему «бинарное»: у каждого узла ровно два направления для движения: - идти влево (если ищем меньшее значение); - идти вправо (если ищем большее значение). Что общего? Оба метода используют один и тот же принцип: 1. на каждом шаге выбор между двумя вариантами; 2. исключение половины возможных вариантов; 3. быстрое сужение области поиска. Таким образом, Бинарный — значит основанный на двух элементах, вариантах или состояниях. Например, мы выбираем чай или кофе :)