Что такое бинарный поиск java
Алгоритм бинарного поиска в Java
Узнайте, как и когда использовать алгоритм бинарного поиска.
1. Обзор
В этой статье мы рассмотрим преимущества бинарного поиска по сравнению с простым линейным поиском и рассмотрим его реализацию в Java.
2. Необходимость эффективного поиска
Допустим, мы занимаемся продажей вина, и миллионы покупателей ежедневно посещают наше приложение.
Через наше приложение клиент может отфильтровать товары, цена которых ниже n долларов, выбрать бутылку из результатов поиска и добавить ее в свою корзину. У нас есть миллионы пользователей, которые каждую секунду ищут вина с ограничением цены. Результаты должны быть быстрыми.
На бэкэнде наш алгоритм выполняет линейный поиск по всему списку вин, сравнивая предельную цену, введенную клиентом, с ценой каждой бутылки вина в списке.
Это означает, что чем больше количество винных бутылок в нашей системе, тем больше времени это займет. Время поиска увеличивается пропорционально количеству введенных новых элементов.
При бинарном поиске время, затраченное на поиск результатов, естественно увеличивается с размером набора данных, но не пропорционально.
3. Бинарный поиск
Проще говоря, алгоритм сравнивает значение key со средним элементом массива; если они неравны, то половина, в которой ключ не может быть частью, исключается, и поиск продолжается для оставшейся половины до тех пор, пока он не будет успешным.
Помните – ключевым аспектом здесь является то, что массив уже отсортирован.
Если поиск заканчивается тем, что оставшаяся половина пуста, то ключа в массиве нет.
3.1. Итеративная Реализация
middle – это средний индекс отсортированного массива . Теперь алгоритм запускает цикл while , сравнивающий ключ со значением массива среднего индекса отсортированного массива .
3.2. Рекурсивная Реализация
Теперь давайте также рассмотрим простую рекурсивную реализацию:
3.3. Использование Arrays.BinarySearch()
3.4. Использование Collections.BinarySearch()
Сортированный список & an Integer | key , который должен быть найден в списке объектов Integer , передаются в качестве аргументов методу BinarySearch класса Java Collections .
3.5. Производительность
Использовать ли рекурсивный или итеративный подход для написания алгоритма-это в основном вопрос личных предпочтений. Но все же есть несколько моментов, о которых мы должны знать:
1. Рекурсия может быть медленнее из – за накладных расходов на поддержание стека и обычно занимает больше памяти
2. Рекурсия не является стеком –
дружественной. Это может вызвать StackOverflowException
при обработке больших наборов данных
3. Рекурсия добавляет ясности коду, так как делает его короче по сравнению с итеративным подходом
В идеале двоичный поиск будет выполнять меньшее количество сравнений в отличие от линейного поиска больших значений n. Для меньших значений n линейный поиск может работать лучше, чем двоичный.
Следует знать, что этот анализ носит теоретический характер и может варьироваться в зависимости от контекста.
Поэтому сначала нам нужно хорошо проанализировать наши требования, а затем принять решение о том, какой алгоритм поиска лучше всего соответствует вашим требованиям.
4. Заключение
Этот учебник продемонстрировал реализацию алгоритма бинарного поиска и сценарий, в котором было бы предпочтительнее использовать его вместо линейного поиска.
Бинарный поиск — Java: Массивы
Наконец перейдем к реальным алгоритмам, для начала рассмотрим один их самых простых – поиск элемента в отсортированном массиве, именно его реализация дает представление о том, как может быть полезна О нотация. Это самая базовая алгоритмическая задача, которую нередко спрашивают на собеседованиях. С одной стороны, для подобных алгоритмов используют уже готовые функции стандартной библиотеки, с другой – подобные вопросы на собеседованиях позволяют узнать полезное о кандидате:
Наивный подход будет выглядеть как перебор элементов в массиве до встречи с нужным, тогда если количество элементов равно n и нужный нам элемент будет последним, нам потребуется сделать n проверок элементов до нахождения нужного, про такой случай и говорят что сложность алгоритма равна O(n).
Рассмотрим другой подход – возьмем средний элемент отсортированного массива и сравним его c искомым. Если элемент меньше – продолжим поиск в левой части массива, если больше в правой, пока не останется нужный элемент. Таким образом нам понадобится число операций равное тому, сколько раз нам нужно поделить массив размером n пополам. Например для массива в 16 элементов мы сначала поделим его на два по 8, потом 8 на два по 4, потом 4 на два по 2 и на конец 2 пополам, те всего 4 операции в худшем случае. Такое число равно двоичному логарифму: число можно столько раз разделить на 2, сколько нужно умножать 2 на 2(возводить в степень) чтобы получить это число.
А логарифм это функция обратная возведению в степень, показывающая сколько же раз нужно умножать 2(возводить в степень), чтобы получить 16.
Код алгоритма будет выглядеть следующим образом:
А использовать данную функцию можно следующим образом:
6 алгоритмов поиска на Java: от простого к сложному
Поиск – распространённое действие, выполняемое в бизнес-приложениях. Под катом лежат реализации известных алгоритмов поиска на Java.
Программирование на Java – всегда интересный экспириенс. Но куда интереснее работать, применяя правильные для конкретных ситуаций алгоритмы.
Реализуем алгоритмы на Java и проанализируем производительность с помощью параметров временной и пространственной сложности.
Линейный поиск
Линейный или последовательный поиск – простейший алгоритм поиска. Он редко используется из-за своей неэффективности. По сути, это метод полного перебора, и он уступает другим алгоритмам.
У линейного поиска нет предварительных условий к состоянию структуры данных.
Объяснение
Алгоритм ищет элемент в заданной структуре данных, пока не достигнет конца структуры.
Реализация
Теперь посмотрим, как реализовать линейный поиск в Java:
Для проверки используем целочисленный массив:
Простой метод для вывода результата:
Временная сложность
Для получения позиции искомого элемента перебирается набор из N элементов. В худшем сценарии для этого алгоритма искомый элемент оказывается последним в массиве.
В этом случае потребуется N итераций для нахождения элемента.
Следовательно, временная сложность линейного поиска равна O(N).
Пространственная сложность
Этот поиск требует всего одну единицу памяти для хранения искомого элемента. Это не относится к размеру входного массива.
Следовательно, пространственная сложность линейного поиска равна O(1).
Применение
Линейный поиск можно использовать для малого, несортированного набора данных, который не увеличивается в размерах.
Несмотря на простоту, алгоритм не находит применения в проектах из-за линейного увеличения временной сложности.
Двоичный поиск
Двоичный или логарифмический поиск часто используется из-за быстрого времени поиска.
Объяснение
Этот вид поиска использует подход «Разделяй и властвуй», требует предварительной сортировки набора данных.
Алгоритм делит входную коллекцию на равные половины, и с каждой итерацией сравнивает целевой элемент с элементом в середине. Поиск заканчивается при нахождении элемента. Иначе продолжаем искать элемент, разделяя и выбирая соответствующий раздел массива. Целевой элемент сравнивается со средним.
Вот почему важно иметь отсортированную коллекцию при использовании двоичного поиска.
Поиск заканчивается, когда firstIndex (указатель) достигает lastIndex (последнего элемента). Значит мы проверили весь массив Java и не нашли элемента.
Есть два способа реализации этого алгоритма: итеративный и рекурсивный.
Временная и пространственная сложности одинаковы для обоих способов в реализации на Java.
Реализация
Итеративный подход
Рекурсивный подход
Теперь посмотрим на рекурсивную реализацию:
Рекурсивный подход отличается вызовом самого метода при получении нового раздела. В итеративном подходе всякий раз, когда мы определяли новый раздел, мы изменяли первый и последний элементы, повторяя процесс в том же цикле.
Другое отличие – рекурсивные вызовы помещаются в стек и занимают одну единицу пространства за вызов.
Используем алгоритм следующим способом:
Временная сложность
Временная сложность алгоритма двоичного поиска равна O(log (N)) из-за деления массива пополам. Она превосходит O(N) линейного алгоритма.
Пространственная сложность
Одна единица пространства требуется для хранения искомого элемента. Следовательно, пространственная сложность равна O(1).
Рекурсивный двоичный поиск хранит вызов метода в стеке. В худшем случае пространственная сложность потребует O(log (N)).
Применение
Этот алгоритм используется в большинстве библиотек и используется с отсортированными структурами данных.
Двоичный поиск реализован в методе Arrays.binarySearch Java API.
Алгоритм Кнута – Морриса – Пратта
Алгоритм КМП осуществляет поиск текста по заданному шаблону. Он разработан Дональдом Кнутом, Воном Праттом и Джеймсом Моррисом: отсюда и название.
Объяснение
В этом поиске сначала компилируется заданный шаблон. Компилируя шаблон, мы пытаемся найти префикс и суффикс строки шаблона. Это поможет в случае несоответствия – не придётся искать следующее совпадение с начального индекса.
Вместо этого мы пропускаем часть текстовой строки, которую уже сравнили, и начинаем сравнивать следующую. Необходимая часть определяется по префиксу и суффиксу, поэтому известно, какая часть уже прошла проверку и может быть безопасно пропущена.
КМП работает быстрее алгоритма перебора благодаря пропускам.
Реализация
Скомпилированный массив Java можно рассматривать как массив, хранящий шаблон символов. Цель – найти префикс и суффикс в шаблоне. Зная эти элементы, можно избежать сравнения с начала текста после несоответствия и приступать к сравнению следующего символа.
Скомпилированный массив сохраняет позицию предыдущего местонахождения текущего символа в массив шаблонов.
Давайте реализуем сам алгоритм:
Здесь мы последовательно сравниваем символы в шаблоне и текстовом массиве. Мы продолжаем двигаться вперёд, пока не получим совпадение. Достижение конца массива при сопоставлении означает нахождение шаблона в тексте.
Но! Есть один момент.
В текстовом шаблоне AAABAAA наблюдается и кодируется в массив шаблонов следующий шаблон:
В подтверждение наших расчётов:
Описанный выше шаблон ясно показан в скомпилированном массиве.
С помощью этого массива КМП ищет заданный шаблон в тексте, не возвращаясь в начало текстового массива.
Временная сложность
Для поиска шаблона алгоритму нужно сравнить все элементы в заданном тексте. Необходимое для этого время составляет O(N). Для составления строки шаблона нам нужно проверить каждый символ в шаблоне – это еще одна итерация O(M).
O (M + N) – общее время алгоритма.
Пространственная сложность
O(M) пространства необходимо для хранения скомпилированного шаблона для заданного шаблона размера M.
Применение
Этот алгоритм используется в текстовых инструментах для поиска шаблонов в текстовых файлах.
Поиск прыжками
От двоичного поиска этот алгоритм отличает движение исключительно вперёд. Имейте в виду, что такой поиск требует отсортированной коллекции.
Прыжки прекращаются, когда найден элемент больше искомого. Затем запускаем линейный поиск между предыдущим и текущим шагами.
Это уменьшает поле поиска и делает линейный поиск жизнеспособным вариантом.
Реализация
Мы начинаем с jumpstep размером с корень квадратный от длины массива и продолжаем прыгать вперёд с тем же размером, пока не найдём элемент, который будет таким же или больше искомого элемента.
Вот так используется алгоритм:
Временная сложность
Пространственная сложность
Искомый элемент занимает одну единицу пространства, поэтому пространственная сложность алгоритма составляет O(1).
Применение
Этот поиск используется поверх бинарного поиска, когда прыжки в обратную сторону затратны.
С ограничением сталкиваются при работе с вращающейся средой. Когда при легком поиске по направлению вперёд многократные прыжки в разных направлениях становятся затратными.
Интерполяционный поиск
Интерполяционный поиск используется для поиска элементов в отсортированном массиве. Он полезен для равномерно распределенных в структуре данных.
При равномерно распределенных данных местонахождение элемента определяется точнее. Тут и вскрывается отличие алгоритма от бинарного поиска, где мы пытаемся найти элемент в середине массива.
Для поиска элементов в массиве алгоритм использует формулы интерполяции. Эффективнее применять эти формула для больших массивов. В противном случае алгоритм работает как линейный поиск.
Реализация
Используем алгоритм так:
Смотрите, как работают формулы интерполяции, чтобы найти 6 :
Теперь давайте применим эти значения к формулам для оценки индекса элемента поиска:
index=0+(7−0)/(8−1)∗(6−1)=5
Элемент integers[5] равен 6 — это элемент, который мы искали. Индекс для элемента рассчитывается за один шаг из-за равномерной распределенности данных.
Временная сложность
В лучшем случае временная сложность такого алгоритма – O(log log N). При неравномерном распределении элементов сложность сопоставима с временной сложностью линейного алгоритма, которая = O(N).
Пространственная сложность
Алгоритм требует одну единицу пространства для хранения элемента для поиска. Его пространственная сложность = O(1).
Применение
Алгоритм полезно применять для равномерно распределенных данных вроде телефонной книги.
Экспоненциальный поиск
Экспоненциальный поиск используется для поиска элементов путём перехода в экспоненциальные позиции, то есть во вторую степень.
В этом поиске мы пытаемся найти сравнительно меньший диапазон и применяем на нем двоичный алгоритм для поиска элемента.
Для работы алгоритма коллекция должна быть отсортирована.
Реализация
Применяем алгоритм Java:
В нашем случае значение диапазона достигается в элементе 8, а элемент в integers[8] равен 95. Таким образом, диапазон, в котором выполняется бинарный поиск:
При этом вызываем бинарный поиск:
Временная сложность
В худшем случае временная сложность этого поиска составит O(log (N)).
Пространственная сложность
Итеративный алгоритм двоичного поиска требует O(1) места для хранения искомого элемента.
Для рекурсивного двоичного поиска пространственная сложность становится равной O(log (N)).
Применение
Экспоненциальный поиск используется с большими массивами, когда бинарный поиск затратен. Экспоненциальный поиск разделяет данные на более доступные для поиска разделы.
Заключение
Каждая система содержит набор ограничений и требований. Правильно подобранный алгоритм поиска, учитывающий эти ограничениях, играет определяющую роль в производительности системы.
В этой статье мы рассмотрели работу алгоритмов поиска Java и случаи их применения.
Бинарный поиск в JavaScript. Практический пример
Что такое бинарный поиск?
Когда нужно выполнить поиск в массиве, простейшим способом может быть использование indexOf() или, возможно, цикла for(). Любой из этих способов будет начинать перебирать массив начиная с начала и переходить по каждому элементу массива до тех пор, пока не будет найдено нужное значение.
Теперь сравним это с бинарным поиском.
Бинарный поиск позволяет выполнять поиск в отсортированном массиве путем многократного разбиения массива пополам.
Бинарный поиск выполняется путем проверки того, является ли искомое значение больше, меньше или равно среднему значению в нашем массиве:
При работе с большими объемами данных гораздо эффективнее использовать бинарный поиск, поскольку при каждой итерации удаляется половина ненужных значений массива, а не только одно неподходящее значение.
Проект
Одним из наиболее важных аспектов диаграммы является подсказка, отображающая соответствующие данные при наведении курсора на диаграмму. При перемещении мыши на подсказке обновляются данные из ближайшей точки диаграммы. Пример:
У нас есть массив всех координат и соответствующих им данных. Координаты находятся внутри объекта, и каждый объект имеет svgX ключ. Выглядит это примерно так:
Изначально я использовал простой цикл for, чтобы сравнить текущую координату X курсора мыши со всеми значениями svgX в моем массиве данных.
Вот как выглядит код цикла for. Мы перебираем все значения svgX, и объект со значением, которое ближе к координате X курсора мыши — это тот объект, данные которого мы хотим показать.
Сначала мы получаем ширину нашего svg элемента и создаем пустой объект для хранения нашей ближайшей точки.
Затем мы перебираем массив данных. Каждое svgX значение объекта в нашем массиве сравнивается с координатой X курсора мыши. Если текущая итерация цикла имеет значение ближе к курсору, чем любая другая итерация, то эта точка устанавливается как наша ближайшая точка.
При небольшом количестве данных этот метод является относительно быстрым. Однако, если у нас есть большой объем данных, этот вариант уже не будет таким эффективным.
Бинарный поиск
Ниже приведен пример кода бинарного поиска для поиска ближайшего значения:
Нам нужно пять основных составляющих для нашего бинарного поиска:
Как видно из приведенного выше кода в строке 10, при запуске бинарного поиска мы передаем на вход весь массив данных, объект мыши, начальную позицию 0 и конечную позицию, равную полному размеру массива:
Когда у нас есть наши данные, середину массива найдем путем деления на два, суммы из начальной и конечной позиций. Чтобы не получить дробь, результирующее число округляется вниз:
Таким образом, середина 0 + (4-0)/2 округленная вниз = 2:
Мы помним, что для этого примера наше целевое значение равно 3,7. После того как мы нашли среднюю позицию, мы проверяем, равна ли она нашему целевому значению. Если это так, мы возвращаем объект, и все готово!
К сожалению, среднее значение массива = 3. А нашей целью является 3,7.
Далее мы проверим, совпадает ли наша конечная позиция — 1, с нашей начальной позицией:
Это условие сработает, когда наш массив уменьшился до двух финальных значений, и наша цель находится между ними. В этом случае мы возвращаем ближнее значение.
На текущей итерации условие вернет false.
Далее мы проверяем, больше ли наше целевое значение за среднее:
Это наш случай! Целевое значение 3,7 больше чем среднее 3. Мы можем избавиться от первых двух значений в нашем массиве:
Используя рекурсию мы возвращаем новый вызов функции binarySearch(). Передаем в функцию наш массив, целевое значение 3,7, среднее значение в качестве начальной позиции и конечное значение в качестве конечной позиции.
Наш новый вызов binarySearch(), будет искать от позиции 2 до data.length-1:
Функция находит новую среднюю позицию data[3]:
Поскольку наше целевое значение 3,7 меньше среднего значения 4, мы отбрасываем правую сторону массива и возвращаем новый вызов функции binarySearch(). На этот раз наша начальная позиция остается data[2], а конечная позиция меняется на среднюю data[3].
Мы дошли до момента, когда наше условие выполнится:
Поскольку наше конечное значение минус единица равняется нашему начальному значению, мы знаем, что целевое значение находится где-то между ними. Мы должны возвратить элемент массива, значение которого ближе к значению 3,7. Поскольку 4 (конечное значение) ближе, то соответственно мы и возвращаем соответствующий элемент: data[3].
Тест скорости
Если объем данных небольшой, рекурсия может быть медленнее, чем цикл for. При тестировании на jsperf с 10 элементами, рекурсивная функция в среднем на 3% медленнее, чем цикл for. Однако при количестве элементов в 10 000, цикл for на 72% медленнее, чем рекурсивная функция. Это означает, что рекурсия практически в два раза быстрее, чем цикл for, и это огромная экономия времени!
Надеюсь, теперь вам понятны основы бинарного поиска в JavaScript!
Бинарный поиск
Представьте, что у вас есть список отсортированных по алфавиту диснеевских героев, и вам нужно найти Микки Мауса.
Линейно это было бы долго. А если воспользоваться «методом разрывания справочника пополам», мы попадаем сразу на Jasmine, и можем смело отбросить первую половину списка, понимая, что Mickey там не может быть.
По этому же принципу отбрасываем второй столбец. Продолжая такую стратегию, мы найдем Микки буквально за пару шагов.
Псевдокод функции бинарного поиска:
Для нашего примера изначально дана такая картинка:
Третья ветка: если значение в midpoint не больше и не меньше, чем key, ему ничего не остается, как быть искомым числом. Его мы и возвращаем в таком случае и заканчиваем работу программы.
Наконец, может статься так, что искомое число и вовсе отсутствует в массиве. Для учёта этого случая делаем такую проверку: