Привет всем! Я опубликовал в своем блоге много статей об алгоритмах и структурах данных, но эта здесь первая. В этой статье мы рассмотрим популярные фундаментальные алгоритмы интервью.
Да, вы угадали: вам нужно реализовать двоичный поиск на Java, и вам нужно написать как итеративный, так и рекурсивный двоичный поиск алгоритмов.
Алгоритм
В информатике двоичный поиск или полуинтервальный поиск — это алгоритм «разделяй и властвуй» , который определяет местонахождение положение элемента в сортировке. Двоичный поиск работает путем сравнения входного значения со средним элементом массива.
Сравнение определяет, равен ли элемент входному, меньше входного или больше входного. Когда сравниваемый элемент равен входному, поиск останавливается и обычно возвращает позицию элемента.
Если элемент не равен входному, то выполняется сравнение, чтобы определить, является ли вход меньше или больше элемента.
В зависимости от результата алгоритм затем запускается снова, но только поиск в верхнем или нижнем подмножестве элементов массива.
Если входные данные не расположены в массиве, алгоритм обычно выводит уникальное значение, указывающее, что это как -1, или просто генерирует исключение RuntimeException в Java, например NoValueFoundException .
Алгоритмы двоичного поиска обычно вдвое сокращают количество проверяемых элементов при каждой последующей итерации, таким образом обнаруживая данный элемент (или определяя его отсутствие) за логарифмическое время.
Кстати, если вы не знакомы с фундаментальными алгоритмами поиска и сортировки, то вы также можете пройти курс вроде Структуры данных в Java: краткое содержание интервью , чтобы узнать, f фундаментальные алгоритмы.
Как написать код итеративного двоичного поиска в Java
Вот пример кода, который показывает логику, лежащую в основе итеративного двоичного поиска в Java . После этого мы будем использовать тот же метод для поиска в массиве с использованием итеративного двоичного поиска:
import java.util.Arrays; import java.util.Scanner;/** * Программа Java для реализации двоичного поиска. * Мы реализовали итеративную * версию алгоритма двоичного поиска в Java * * @author Javin Paul */public class IterativeBinarySearch {public static void main (String args []) {int [] list = new int [] {23, 43, 31, 12}; int number = 12; Arrays.sort (список); System.out.printf ("Двоичный поиск% d в целочисленном массиве% s% n", число, Arrays.toString (список)); binarySearch (список, 12); System.out.printf ("Двоичный поиск% d в целочисленном массиве% s% n", 43, Arrays.toString (список)); binarySearch (список, 43); список = новый интервал [] {123, 243, 331, 1298}; число = 331; Arrays.sort (список); System.out. printf ("Двоичный поиск% d в целочисленном массиве% s% n", число, Arrays.toString (список)); binarySearch (список, 331); System.out.printf ("Двоичный поиск% d в целочисленном массиве% s% n", 331, Arrays.toString (список)); binarySearch (список, 1333); //Использование Core Java API и инфраструктуры коллекций//Предварительное условие для Arrays.binarySearch Arrays.sort (list); //Поиск элемента int index = Arrays.binarySearch (list, 3);}/** * Выполнение двоичного поиска в отсортированном массиве в Java * @param input * @param number * @ return location элемента в массиве */public static void binarySearch (int [] input, int number) {int first = 0; int last = input.length - 1; int средний = (первый + последний)/2; в то время как (первый last) {System.out.println (число + "отсутствует в списке. n"); }}}
Вот и все о как реализовать двоичный поиск без использования рекурсии в Java . Наряду с линейным поиском, это два основных алгоритма поиска, которые вы изучите на занятиях по информатике.
Структура данных двоичного дерева поиска использует преимущества этого алгоритма и упорядочивает данные в иерархической структуре таким образом, чтобы что вы можете искать любой узел в O ( l o g N ) O (logN) O (logN) time.
Вы должны помнить, что для использования двоичного поиска вам необходимо отсортированный список или массив ; поэтому вам также необходимо учитывать стоимость сортировки, когда вы рассматриваете возможность использования алгоритмов двоичного поиска в реальном мире.
