Цель: В конце этой статьи вы должны быть в состоянии: понимать и уметь реализовывать как линейные, так и двоичные алгоритмы поиска, используя как рекурсивную, так и итеративную версию, понимать временную сложность, связанную с каждым из них, и различия между ними.
Мы собираемся реализовать наш первый алгоритм по методу поиска, называемому методом бинарного поиска; и на самом деле, если вы находитесь на этом уровне, я уверен, что вы уже написали свой первый алгоритм, возможно, вы этого не осознаете, но вы это сделали.
Сценарий://объявление и назначение массива
int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
Вопрос: Найдите мне индекс числа 5 из заданного массива, обр. выше? Как человек, вы можете начать с любого конца, слева или справа, и последовательно двигаться, чтобы получить номер 5, отслеживая индекс. Вы выполняете алгоритм, называемый линейным алгоритмом.
Вы можете достичь того же алгоритма, используя циклы; и я собираюсь использовать цикл for для этой демонстрации. Давайте создадим метод, вызывающий линейный поиск ниже
public static int linearSearch(int[] list, int value) {
/*
* takes int array and int value
* return the index of the value if found
* otherwise -1 indicating not found
*/
//declare current element
int currEl;
for (int i = 0; i < list.length; i++) {
// Assigning current element
currEl = list[i];
//checking whether we found value to return its index
if(currEl == value) return i;
}
/*
* after searched through the entire array, list * return not found index, -1
*/
return -1;
}
}
Это был метод линейного поиска. Мы начали поиск слева от массива и последовательно искали каждый элемент в массиве, чтобы проверить, соответствует ли это искомому значению, если это так, мы возвращаем его индекс, в противном случае он не найден в массиве после того, как мы проверили все элементы в массиве, поэтому мы возвращаем -1, указывающий, что он не найден.
Анализ сложности алгоритма, связанного с этим методом
Тест: укажите количество необходимых шагов Помните, что искусство – это переменная нашего массива выше
Сколько N шагов нам потребуется, чтобы найти первый элемент, 1 в массиве, arr? 1 шаг, ты понял! Это то, что мы назвали наилучшим сценарием, независимо от длины массива, нам всегда потребуется один шаг, чтобы найти первый элемент в массиве В обозначении Big Ohh, его O (1), операция с постоянным временем, Сколько N шагов нам потребуется, чтобы найти элемент, которого не существует в массиве, обр.? 10 шагов, правильно! Поскольку нам нужно выполнить поиск по всему массиву, arr, который займет у нас 10 раз, прежде чем вернуться не найдено, -1 Сколько N шагов потребуется, если элементы, которых не существует в arr, если arr увеличивается до N элементов? N шагов, Блестящий В обозначении Big Oh это представлено как O(N), линейная временная сложность
Лучший способ поиска элемента в массиве!
Мы можем сделать поиск лучше, фактически используя алгоритм, называемый бинарным поиском. Алгоритм двоичного поиска уменьшает проблему вдвое при очень быстром поиске! Ты этого не понимаешь, это круто, я тоже не понимаю. Просто шучу, Однако сделай мне одолжение, улыбнись! Отлично, давайте продолжим.
Давайте опустим наш массив выше
int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
Сначала, когда я попросил вас найти мне индекс элемента 5 из массива, вы начали с одного конца, возможно, слева, и собирались последовательно найти индекс элемента 5. Этот подход был отличным, но дорогим по сравнению с этим подходом к бинарному поиску, он же алгоритм “разделяй и властвуй”. На этот раз я хочу, чтобы вы начали поиск с середины, это математический этаж (об.длина/2) Я использую Math.floor(float) для округления значения в случае плавающей цифры; и не волнуйтесь, если вы присваиваете arr.length/2 переменной int, которая неявно округлит ее для вас. например, int mid = (длина об./2);
В то время как ; и мы ищем элемент 5, ОБРАТИТЕ ВНИМАНИЕ: середина – это индекс.
Наш первый поиск дает нам элемент 6, пока мы ищем элемент 5, а затем что мы делаем? Прямо на наш взгляд, мы должны знать, что элемент 5 никогда не может быть найден по среднему индексу и выше, потому что все они больше элемента 5; Следовательно, элемент 5 должен иметь некоторый индекс ниже среднего индекса. Это интересно, давайте отбросим ненужную правую половину массива. Это наш нарезанный массив ниже.
arr = {1, 2, 3, 4, 5};
повторяя тот же шаг; mid = (об.длина/2); сравнивая элемент 3 с элементом 5, мы знаем, что элемент 5 больше элемента 3, следовательно, его нельзя найти ни по одному индексу в середине и ниже. Итак, давайте отбросим все элементы формы посередине и ниже
arr = {4, 5};
повторяя тот же подход; mid = (arr.длина/2); сравнивая arr[mid], который является элементом 5, с элементом 5, который мы ищем, они одинаковы, поэтому мы должны вернуть середину. Ааааа, улыбнись, ты нашел это и передумал; Однако мы столкнулись с ошибкой, называемой ошибкой индекса, на самом деле нет; Обратите внимание, это возвращает индекс 1, потому что именно там был найден элемент 5 в недавнем массиве, обр. Принимая во внимание, что в исходном/первом массиве элемент 5 находится под индексом 4, это правильный индекс, и это то, что мы хотели вернуть. Этот подход вполне подходит, если мы просто проверяем наличие элемента в массиве; возвращаем true, если найдено другое значение false; но поскольку мы заботимся об индексе элемента, который мы ищем, мы должны позаботиться о наших индексах. Это потребовало бы от нас еще двух переменных, давайте назовем их низкими и высокими для сопоставления наших низких и высоких индексов соответственно.
Вот код концепции, которую мы объяснили до сих пор. Обратите внимание, что приведенный ниже код не заботится об индексе. Функция вернет значение true, если элемент найден, в противном случае значение false. Я собираюсь реализовать его рекурсивно, и я хотел бы, чтобы вы реализовали его с помощью цикла.
Вывод: вы получаете это только делая, а не наблюдая. Концепции имеют значение, но практические теории побеждают.
public static boolean binarySearch_recursive(int[] arr, int find) {
if(arr.length < 1) return false;
// for an empty array we're done
int mid = arr.length / 2; // our mid index
if(arr[mid] == find) return true;
else if(arr.length == 1) return arr[mid] == find;
else {
if(arr[mid] < find) { // ignore the left halve
arr = Arrays.copyOfRange(arr, mid + 1, arr.length);
return binarySearch_recursive(arr, find);
}
// ignore the right halve
arr = Arrays.copyOfRange(arr, 0, mid);
// slicing an array
return binarySearch_recursive(arr, find);
}
}
Мы многое сделали, я призываю вас сделать перерыв здесь хотя бы на 7 минут, а когда вы вернетесь, мы рассмотрим бинарный поиск, который учитывает индексы.
С возвращением! Надеюсь, вы реализовали свою циклическую версию приведенного выше кода, если вы этого не сделаете, я призываю вас вернуться и попробовать. Не просто читайте, читайте и практикуйтесь! Если вы пробовали и все еще не поняли, не стесняйтесь гуглить. На самом деле, когда я писал эту статью, я погуглил “нарезка массива в java” и stackoverflow.com было полезно.
Хватит разговоров, давайте кодировать!
На этот раз я собираюсь реализовать метод двоичного поиска, который возвращает индекс элемента, если он найден, или -1, если не найден. Я собираюсь использовать циклическую версию, и вам рекомендуется реализовать ее рекурсивную версию.
public static int binarySearchIteratively(int[] a, int key) {
int high = a.length;
int low = 0;
int mid = (high + low) / 2;
while (low <= high) {
if(key == a[mid]) return mid;
else if(a[mid] < key) {
// search right
low = mid + 1;
mid = (high + low) / 2;
}else {// search left
high = mid – 1;
mid = (high + low) / 2;
}
}
return -1;
}
Краткое объяснение кода, который мы назначили: high – длина массива low – индекс 0 mid = (низкий + высокий)/2 примечание, поскольку mid является переменной int, существует неявное разделение по этажам, которое защищает нас от использования Math.floor(float)
цикл while будет продолжаться до тех пор, пока он будет низким, и это очень важно. Внутри цикла while мы обновляем low, high и mid в зависимости от того, какую часть искать после сравнения нашего ключа с [mid].
Сложность во время выполнения:
Мы уже объясняли это выше или, если вы могли бы понаблюдать за кодом, для каждой итерации мы уменьшаем проблему вдвое, то есть отбрасываем ненужную часть. Т.е. для первой итерации проблема теперь N/2, вторая итерация N/4 или (N/2)/2 и так далее. Это в асимптотической нотации, известной как Big Oh, равно O (LOGN), сложности логарифмов.
Полезно знать: Знаете ли вы, что первый бинарный поиск был опубликован в 1946 году, а первый без ошибок был опубликован в 1962 году. В функции Java Arrays.BinarySearch() была обнаружена ошибка, обнаруженная в 2006 году.
Линейный поиск против Бинарного поиска! Мы знаем, что двоичный поиск является более быстрым алгоритмом с точки зрения временной сложности, однако его можно использовать только для отсортированного массива. Это привело нас к другим темам, алгоритмам сортировки, мы перейдем к тому, где мы будем реализовывать быструю сортировку, сортировку слиянием, сортировку по выбору, сортировку по пузырькам и сортировку по глупости/ошибке.
Это все для части 1 нашего обзора структуры данных и алгоритма.
Вы можете ознакомиться со второй частью здесь
Автор Fabala Диббаси в Твиттере в LinkedIn
Оригинал: “https://dev.to/fabaladibbasey/data-structures-and-algorithms-walk-through-part-1-linear-and-binary-algorithm-27g1”