Вступление
От выбора заветной пары джинсов из гардероба до выбора следующего фильма для просмотра с партнером - человеческая жизнь наполнена поисками вещей.
В повседневной жизни люди обычно ищут между несколькими, если не дюжиной, предметами. Компьютерам приходится иметь дело с поиском данных в сравнительно огромных объемах с точки зрения их размера и количества.
Это гарантирует, что компьютеру необходим эффективный метод для максимально эффективного поиска внутри своих массивов и коллекций.
Возможность найти информацию среди коллекции - одна из основных функциональных точек приложения.
Бинарный поиск
Двоичный поиск (иногда известный как логарифмический поиск ) - широко популярный алгоритм поиска в отсортированном массиве позиции заданного элемента.
Он работает по принципу «разделяй и властвуй », сравнивая целевой элемент со средним элементом массива. В случае обнаружения совпадения возвращается его позиция, в противном случае, если целевой элемент меньше среднего элемента, он не может находиться справа от среднего элемента.
Следовательно, правая половина массива (включая средний элемент) отбрасывается, и поиск продолжается в левой половине с использованием того же подхода.
Точно так же, если целевой элемент больше среднего элемента, он не может находиться в месте, предшествующем середине массива. Поэтому левая половина массива отбрасывается, а поиск продолжается в правой половине.
Это повторяется до тех пор, пока не будет найдено совпадение.
Мы можем сделать это предположение просто потому, что знаем, что массив предварительно отсортирован. Если бы он не был отсортирован, мы не смогли бы реализовать двоичный поиск.
Вот визуальное представление того, как работает двоичный поиск:
{.ezlazyload}
Выполнение
Поскольку у нас есть повторяющийся шаг (проверка среднего элемента и отбрасывание одной половины массива), мы можем реализовать алгоритм, используя два подхода - итерационный подход и рекурсивный подход.
Как обычно, между этими двумя нет явного победителя, и вы можете использовать любой из них в зависимости от ваших личных предпочтений.
Итеративный
Начнем с итеративной реализации:
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;
}
Нам нужно отслеживать lowIndex (первый индекс) и highIndex
(последний индекс), чтобы получить среднее арифметическое значение для
массива. elementPos по умолчанию равен -1 что означает, что элемент
не был найден.
Если нет, мы просто возвращаем эту позицию. Если это так, мы
корректируем elementPos чтобы отразить расположение в массиве.
Затем, через в 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;
}
Бенчмаркинг двоичного поиска
Чтобы проанализировать, насколько эффективно алгоритм двоичного поиска работает с заданными целочисленными наборами данных, давайте запустим код для целочисленных массивов различного размера и понаблюдаем за временем выполнения, которое требуется для двоичного поиска, чтобы найти заданное число, выраженное в наносекундах:
Размер массива 1-й прогон (нс) 2-й прогон (нс) 3-й проход (нс) Среднее (нс) 10 568 500 755 000 644 700 656 066 100 846 100 713 000 724 100 761 066 1000 1,323,600 942 900 735 800 1 000 766
Анализ Big-O
На каждой итерации поиска двоичный поиск уменьшает вдвое набор элементов, которые он ищет. Это приводит к тому, что алгоритм двоичного поиска сохраняет эффективность логарифмического времени наихудшего случая. В терминах Big-O Notation , сложность O (log n).
Более того, если целевой элемент был найден в самой середине массива с первого раза, операция завершилась бы за линейное время . Из этого мы можем сделать вывод, что эффективность двоичного поиска в лучшем случае равна O (1) .
Следовательно, окончательный алгоритм двоичного поиска имеет среднюю производительность O (log n) .
Также важно отметить, что, хотя алгоритм очень эффективен для поиска в массивах, его логика требует предварительной сортировки искомого массива.
Если вы планируете использовать алгоритм для несортированного массива, вам придется сначала отсортировать его, что приведет к увеличению сложности. В этом случае даже типичный линейный поиск обычно преобладает над двоичным поиском с его сложностью O (n).
Заключение
С момента первого упоминания в 1946 году Джона Мочли , двоичный поиск сохранился до сих пор как простой для понимания и высокоэффективный алгоритм поиска в отсортированных массивах позиций его целевых элементов.
Он работает по принципу «разделяй и властвуй », сравнивая целевой элемент со средним элементом массива. В этой статье мы реализовали итеративный и рекурсивный подходы и протестировали алгоритм с тремя различными наборами целых чисел.
Кроме того, мы провели быстрый анализ Big-O, чтобы доказать эффективность этого базового, но эффективного алгоритма поиска.