Бинарный поиск на Java

Один их самых простых алгоритмов – это поиск элемента в отсортированном массиве. Это самая базовая алгоритмическая задача, которую нередко спрашивают на собеседованиях

· 2 минуты на чтение

С одной стороны, для подобных алгоритмов используют уже готовые функции стандартной библиотеки, с другой – подобные вопросы на собеседованиях позволяют узнать полезное о кандидате.

Первое что приходи на ум: перебор элементов в массиве до нужного, тогда если количество элементов равно n и нужный нам элемент будет последним, нам потребуется сделать n проверок элементов до нахождения нужного, про такой случай и говорят что сложность алгоритма равна O(n).

Рассмотрим другой подход - бинарный поиск – возьмем средний элемент отсортированного массива и сравним его c искомым. Если элемент меньше – продолжим поиск в левой части массива, если больше в правой, пока не останется нужный элемент. Таким образом нам понадобится число операций равное тому, сколько раз нам нужно поделить массив размером n пополам.

Например, для массива в 16 элементов мы сначала поделим его на два по 8, потом 8 на два по 4, потом 4 на два по 2 и на конец 2 пополам, те всего 4 операции в худшем случае. Такое число равно двоичному логарифму.

Спонсор поста

Без рекурсии

public class Binary {

    public static void main(String[] args) {
        int[] values = {1, 1, 2, 3, 4, 10};
        int valueToFind = 3;

        System.out.printf("Index = %d%n", binarySearch(values, valueToFind, 0, values.length - 1));
    }

    private static int binarySearch(int[] sortedArray, int valueToFind, int low, int high) {
        int index = -1;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (sortedArray[mid] < valueToFind) {
                low = mid + 1;
            } else if (sortedArray[mid] > valueToFind) {
                high = mid - 1;
            } else if (sortedArray[mid] == valueToFind) {
                index = mid;
                break;
            }
        }
        return index;
    }

}

С использованием рекурсии

public class Binary {

    public static void main(String[] args) {
        int[] values = {1, 1, 2, 3, 4, 10};
        int valueToFind = 3;

        System.out.printf("Index = %d%n", binarySearch(values, valueToFind, 0, values.length - 1));
    }

    private static int binarySearch(int[] values, int valueToFind, int l, int r) {
        if (l == r) {
            return (values[l] == valueToFind) ? l : -1;
        }

        int m = l + (r - l) / 2;

        if (valueToFind > values[m]) {
            return binarySearch(values, valueToFind, m + 1, r);
        } else if (values[m] > valueToFind) {
            return binarySearch(values, valueToFind, l, m - 1);
        }
        return m;
    }

}

Если элемент не найден, то вернется -1.

m = l + (r - l) / 2;

Во многих примерах в интернете можно встретить запись int m = (l + r) / 2;, вместо int mid = l + (r - l) / 2;. И у меня в заметке тоже была такая запись, пока один из читателей не обратил на это внимание.

Но использование второго варианта является лучшей практикой, так как это помогает избежать переполнения, когда размер массива велик.

Например, если l = 2147483647 и r = 2147483647, сумма l и r будет равна 4294967294, что превышает максимальное значение, которое может удерживать int, вызывая переполнение.

С другой стороны, если вы используете mid = l + (r - l) / 2; это будет работать, как и ожидалось, потому что вычитание будет сделано первым, а результат будет равен нулю, поэтому деление будет равно нулю, а сложение вернет значение l.

Struchkov Mark
Struchkov Mark
Задавайте вопросы, если что-то осталось не понятным👇