Бинарный поиск на отсортированном массиве

11 апреля 2022

Содержание

Простая реализация
Обобщённая реализация
Тестирование

В задачах на применение классических алгоритмов часто используют бинарный (двоичный) поиск. Его можно применять только на предварительно отсортированном массиве. Самый простой алгоритм сортировки см. в статье Пузырьковая сортировка.

Суть бинарного поиска можно описать как «разделяй и властвуй». Исходный отсортированный по порядку массив мы делим пополам и проверяем элемент посередине. Если он равен тому, который мы ищем, то возвращаем его индекс. Если не равен, то проверяем границы и выбираем ту половину, в которой искомый элемент может находиться и выполняем проверку снова. Так мы сужаем область поиска до тех пор, пока левая граница не станет равна правой. Если элемент не удалось найти, возвращаем -1.

Простая реализация

Рассмотрим реализацию на Java на примере массива целых чисел:

int binarySearch(int[] sortedArray, int element) {
    // в начале левая и правая границы равны первому и последнему элементу массива
    var left = 0;
    var right = sortedArray.length - 1;
    // пока левая и правая границы поиска не пересеклись
    while (left <= right) {
        // индекс текущего элемента находится посередине
        var middle = (left + right) / 2;
        var current = sortedArray[middle];

        if (current == element) {
            // нашли элемент - возвращаем его индекс
            return middle;
        } else if (current < element) {
            // текущий элемент меньше искомого - сдвигаем левую границу
            left = middle + 1;
        } else {
            // иначе сдвигаем правую границу
            right = middle - 1;
        }
    }
    // проверили весь массив, но не нашли элемент
    return -1;
}

Поиск будет выполнен довольно быстро. В О-нотации сложность алгоритма равна O(log(N)). Тогда как если бы искали элемент прямым перебором, проверяя последовательно каждый элемент, то сложность была бы O(N), т.е. кратная количеству элементов.

Обобщённая реализация

Обобщённая реализация не сильно будет отличаться от исходной. Параметризуем метод binarySearch() типом T, реализующим стандартный интерфейс Comparable. На вход принимаем массив из элементов типа T. Искать будем также элемент типа T.

<T extends Comparable<T>> int binarySearch(T[] sortedArray, T element) {
    var left = 0;
    var right = sortedArray.length - 1;
    while (left <= right) {
        var middle = (left + right) / 2;
        var current = sortedArray[middle];
        // ключевое отличие
        var compareResult = current.compareTo(element);
        if (compareResult == 0) {
            return middle;
        } else if (compareResult < 0) {
            left = middle + 1;
        } else {
            right = middle - 1;
        }
    }
    return -1;
}

Ключевым отличием здесь является использование метода compareTo() из интерфейса Comparable. Результат его работы мы сравниваем с нулём:

если результат равен нулю – элементы равны.
если результат меньше нуля – левый элемент меньше правого.
если больше нуля – левый больше правого.

Этот контракт легко запомнить, если в условии мысленно заменить compareResult и 0 на left и right соответственно.

Тестирование

Вы можете самостоятельно протестировать данную реализацию на пустом массиве, на массиве содержащем искомый элемент и на массиве его не содержащем.

А мы выполним следующий синтетический тест: сгенерим массив из миллиона элементов, где значение элемента равно его индексу, умноженному на 10. То есть он заведомо отсортирован по возрастанию. Элементы массива будут иметь тип BigInteger, реализующий интерфейс Comparable. Поищем средний элемент со значением 500 000.

// генерим массив из 1 миллиона чисел, идущих по порядку
var sortedArray = new BigInteger[1_000_000];
for (var i = 0; i < 1_000_000; i++) {
sortedArray[i] = BigInteger.valueOf(i).multiply(BigInteger.TEN);
}
System.out.println(binarySearch(sortedArray, BigInteger.valueOf(500_000L))); // вернёт индекс 50 000

Как видите, отличия в реализации простого и обобщённого метода минимальны.

Облако тэгов

Kotlin, Java, Spring, Spring Boot, Spring Data, SQL, PostgreSQL, Oracle, Linux, Hibernate, Collections, Stream API, многопоточность, файлы, Nginx, Apache, maven, gradle, JUnit, YouTube, новости, руководство, ООП, алгоритмы, головоломки, rest, GraphQL, Excel, XML, json, yaml.

Бинарный поиск на отсортированном массиве

Содержание

Простая реализация

Обобщённая реализация

Тестирование

Облако тэгов

Последние статьи

Комментарии

Добавить комментарий