Автор оригинала: Dasun Nirmitha.
Вступление
Начиная с выбора заветной пары джинсов из вашего гардероба и заканчивая выбором следующего фильма для просмотра с вашим партнером, человеческая жизнь наполнена поиском вещей.
В то время как в повседневной жизни люди обычно ищут между несколькими, если не дюжиной предметов. Компьютерам приходится иметь дело с поиском данных в сравнительно больших объемах с точки зрения их размера и количества.
Это гарантирует, что компьютер должен иметь эффективный метод для максимально эффективного поиска в своих массивах и коллекциях.
Возможность находить информацию в коллекции-один из самых основных функциональных моментов приложения.
Двоичный поиск
Двоичный поиск (иногда известный как Логарифмический поиск ) – широко популярный алгоритм поиска отсортированного массива по положению заданного элемента.
Он работает на основе разделяй и властвуй , сравнивая целевой элемент со средним элементом массива. В случае обнаружения совпадения – возвращается его позиция, в противном случае, если целевой элемент меньше среднего элемента, он не может находиться справа от среднего элемента.
Поэтому правая половина массива (включая средний элемент) отбрасывается, и поиск продолжается в левой половине, используя тот же подход.
Аналогично, если целевой элемент больше среднего элемента, он не может находиться в месте, предшествующем середине массива. Поэтому левая половина массива отбрасывается, а поиск продолжается в правой половине.
Это повторяется до тех пор, пока не будет найдено совпадение.
Мы можем сделать это предположение просто потому, что знаем, что массив отсортирован заранее. Если бы он не был отсортирован, мы не смогли бы реализовать двоичный поиск.
Вот наглядное представление того, как работает двоичный поиск:
Реализация
Поскольку у нас есть повторяющийся шаг (проверка среднего элемента и отбрасывание одной половины массива), мы можем реализовать алгоритм, используя два подхода – итеративный подход и рекурсивный подход.
Как обычно, между этими двумя нет явного победителя, и вы можете выбрать любой из них, основываясь на своих личных предпочтениях.
Повторяющийся
Давайте начнем с итеративной реализации:
public static int iterativeSearch(int[] arrayToSearch, int element) {
int lowIndex = 0;
int highIndex = arrayToSearch.length-1;
// Holds the position in array for given element
// Initial negative integer set to be returned if no match was found on array
int elementPos = -1;
// If lowIndex less than highIndex, there's still elements in the array
while (lowIndex <= highIndex) {
int midIndex = (lowIndex + highIndex) / 2;
if (element == arrayToSearch[midIndex]) {
elementPos = midIndex;
break;
} else if (element < arrayToSearch[midIndex]) {
highIndex = midIndex-1;
} else if (element > arrayToSearch[midIndex]) {
lowIndex = midIndex+1;
}
}
return elementPos;
}
Нам нужно отслеживать низкий индекс (первый индекс) и высокий индекс (последний индекс), чтобы получить среднее арифметическое для массива. Элемент Pos по умолчанию равен -1 что означает, что элемент не был найден.
Если этого не произошло, мы просто возвращаем эту позицию. Если это так, мы корректируем элемент Pos , чтобы отразить местоположение в массиве.
Затем, через цикл while , мы проверяем, является ли средний элемент тем, который мы ищем. Если нет, мы настраиваем lowIndex и highIndex , чтобы игнорировать половину массива, в котором нет целевого элемента.
Рекурсивный
Рекурсивная реализация тоже довольно проста, но мы просто вызываем метод рекурсивно, пока элемент не будет найден:
public static int recursiveSearch(int[] arrayToSearch, int element) {
return recursiveSearch(arrayToSearch, element, 0, arrayToSearch.length-1);
}
private static int recursiveSearch(int[] arrayToSearch, int element, int lowIndex, int highIndex) {
// If lowIndex surpasses highIndex, the element has not been found
if (lowIndex > highIndex) return -1;
// Default assumption is that the element is not found
int elementPos = -1;
int midIndex = (lowIndex + highIndex) / 2;
if (element == arrayToSearch[midIndex]) {
elementPos = midIndex;
} else if (element < arrayToSearch[midIndex]) {
recursiveSearch(arrayToSearch, element, lowIndex, midIndex-1);
} else if (element > arrayToSearch[midIndex]) {
recursiveSearch(arrayToSearch, element, midIndex+1, highIndex);
}
return elementPos;
}
Сравнительный Анализ Бинарного Поиска
Чтобы проанализировать, насколько эффективно алгоритм двоичного поиска работает с заданными целочисленными наборами данных, давайте запустим код с целочисленными массивами различных размеров и понаблюдаем за временем выполнения, которое требуется для двоичного поиска, чтобы найти заданное число, выраженное в наносекундах:
| 10 | 568500 | 755000 | 644700 | 656066 |
| 100 | 846100 | 713000 | 724100 | 761066 |
| 1000 | 1323600 | 942900 | 735800 | 1000766 |
Анализ Big-O
На каждой итерации поиска Двоичный поиск делит пополам набор элементов, которые он ищет. Это приводит к тому, что алгоритм двоичного поиска сохраняет наихудшую эффективность логарифмического времени . В Терминах обозначения Big-O , an O(log n) сложность.
Более того, в случае, если целевой элемент был найден в самой середине массива при первом заходе, операция была бы завершена за линейное время . Из этого мы можем сделать вывод, что двоичный поиск имеет наилучшую эффективность в случае O(1) .
Git Essentials
Ознакомьтесь с этим практическим руководством по изучению Git, содержащим лучшие практики и принятые в отрасли стандарты. Прекратите гуглить команды Git и на самом деле изучите это!
Следовательно, окончательно бинарный алгоритм поиска имеет среднюю производительность O(log n) .
Также важно отметить, что, хотя алгоритм очень эффективен для поиска массивов, его логика требует, чтобы искомый массив был предварительно отсортирован.
В случае, если вы планируете использовать алгоритм для несортированного массива, вам сначала придется его отсортировать, что приведет к увеличению сложности. В этом случае даже типичный линейный поиск, как правило, будет доминировать в двоичном поиске с его O(n) сложностью.
Вывод
С момента первого упоминания в далеком 1946 году Джоном Мочли Двоичный поиск по сей день сохраняется как простой для понимания и высокоэффективный алгоритм поиска отсортированных массивов по позициям его целевых элементов.
Он работает на основе разделяй и властвуй , сравнивая целевой элемент со средним элементом массива. В этой статье мы реализовали как итерационный, так и рекурсивный подходы и сравнили алгоритм с тремя различными наборами целых чисел.
Кроме того, мы провели быстрый анализ Big-O, чтобы доказать эффективность этого базового, но эффективного алгоритма поиска.