Алгоритмы поиска и сортировки - это популярные алгоритмы на любых языках программирования. Они являются основой для понимания основ программирования. Одним из таких популярных алгоритмов поиска является двоичный поиск в . В этой статье я расскажу все о его реализации.
В этой статье рассматриваются следующие темы:
Давайте начнем!
Что такое двоичный поиск?
Бинарный поиск в это алгоритм поиска, который находит позицию целевого значения в отсортированном массив . Бинарный поиск сравнивает целевое значение со средним элементом массива. Этоработает только с отсортированным набором элементов. Чтобы использовать двоичный поиск в коллекции, сначала нужно отсортировать.
Когда используется для выполнения операций с отсортированным набором, количество итераций всегда можно уменьшить в зависимости от значения, которое ищется. На приведенном выше снимке показано, как найти средний элемент . Аналогия с двоичным поиском заключается в использовании информации о сортировке массива и уменьшении временной сложности до O (журнал n) .
Реализация алгоритма двоичного поиска
Давайте посмотрим на приведенный ниже псевдокод, чтобы лучше понять его.
Процедура binary_search A & larr отсортированный массив n & larr размер массива x & larr значение для поиска Установить низкий = 1 Установить высокий = n, в то время как x не найден, если высокийПояснение:
Шаг 1: Сначала сравните x со средним элементом.
Шаг 2: Если x соответствует среднему элементу, вы должны вернуть средний индекс.
Шаг 3: Иначе, если x больше среднего элемента, то x может лежать только в правой половине массива после среднего элемента. Следовательно, вы повторяете правую половину.
Шаг 4: В противном случае, если (x меньше), то повторяется для левой половины.
Вот как вам нужно искать элемент в данном массиве.
объявление массива объектов в javaДавайте теперь посмотрим, как рекурсивно реализовать алгоритм двоичного поиска. Программа ниже демонстрирует то же самое.
Рекурсивный двоичный поиск
public class BinarySearch {// Реализация рекурсивного двоичного поиска в Java // Возвращает индекс x, если он присутствует в arr [l..h], иначе возвращает -1 int binarySearch (int a [], int l, int h, int x) {if (h> = l) {int mid = l + (h - l) / 2 // Если элемент присутствует в самом центре if (a [mid] == x) return mid // Если элемент меньше mid, то он может присутствовать только в левом подмассиве if (a [mid]> x) return binarySearch (arr, l, mid - 1, x) // Иначе элемент может присутствовать только в правом подмассиве return binarySearch (arr, mid + 1, h, x)} // Мы достигаем этого, когда элемент отсутствует в массиве return -1} public static void main (String args []) {BinarySearch ob = new BinarySearch () int a [] = {20, 30, 40, 10, 50} int n = a.length int x = 40 int res = ob.binarySearch (a, 0, n - 1, x) if (res == -1) System.out .println ('Элемент отсутствует') else System.out.println ('Элемент найден по индексу' + res)}}При выполнении вышеуказанной программы он найдет элемент, присутствующий в конкретном индексе
Элемент найден с индексом 2Итак, это подводит нас к концу двоичного поиска в Ява статья. Я надеюсь, что вы нашли его информативным и помогли вам понять .
Проверьте от Edureka, надежной компании по онлайн-обучению с сетью из более чем 250 000 довольных учащихся по всему миру. Мы здесь, чтобы помочь вам на каждом этапе вашего пути, чтобы стать помимо этого java-интервью вопросами. Мы разработали учебную программу, предназначенную для студентов и профессионалов, желающих стать Java-разработчиком. Курс разработан, чтобы дать вам хорошее начало в программировании на Java и обучить вас как основным, так и продвинутым концепциям Java, а также различным средам Java, таким как Hibernate и Spring.
Если у вас возникнут трудности при реализации двоичного поиска в , пожалуйста, укажите это в разделе комментариев ниже и мы свяжемся с вами в ближайшее время.