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

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

Первое что приходи на ум: перебор элементов в массиве до нужного, тогда если количество элементов равно 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) / 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) / 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