Интервьюер, я напишу метод бинарного поиска! Да тот, что без багов!

алгоритм

Предисловие научно-популярное

Первая статья о бинарном поиске была опубликована в 1946 году, но первый безошибочный метод бинарного поиска появился в 1962 году, с интервалом в 16 лет.

Сможете ли вы в 2019 году написать метод бинарного поиска без ошибок в процессе собеседования?

определение

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

Процесс поиска начинается со среднего элемента массива, и если средний элемент является именно тем элементом, который нужно найти, процесс поиска заканчивается;

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

Если на каком-то шаге массив пуст, значит, он не найден.

Этот алгоритм поиска уменьшает диапазон поиска наполовину для каждого сравнения.

бинарный поисковый код

В соответствии с вышеприведенным определением попробуем написать код метода бинарного поиска.

public static int binary(int[] arr, int data) {
        int min = 0;
        int max = arr.length - 1;
        int mid;
        while (min <= max) {
            mid = (min + max) / 2;
            if (arr[mid] > data) {
                max = mid - 1;
            } else if (arr[mid] < data) {
                min = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

Теперь я спрашиваю вас, есть ли проблема с приведенным выше кодом? Какой код глючит?

Пожалуйста, подумайте об этом через минуту.

Для приведенного выше кода проблема находится в строке 6:

mid = (min + max) / 2;

Этот код будет переполняться, когда min и max будут большими, что приведет к ошибке доступа к массиву.

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

Как это улучшить? Общий подход таков:Превратите сложение в вычитание.

public static int binary(int[] arr, int data) {
        int min = 0;
        int max = arr.length - 1;
        int mid;
        while (min <= max) {
            // 防止溢出
            mid =  min + (max - min) / 2;
            if (arr[mid] > data) {
                max = mid - 1;
            } else if (arr[mid] < data) {
                min = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

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

 public static int binary(int[] arr, int data) {
        int min = 0;
        int max = arr.length - 1;
        int mid;
        while (min <= max) {
            // 无符号位运算符的优先级较低，先括起来
            mid =  min + ((max - min) >>> 1);
            if (arr[mid] > data) {
                max = mid - 1;
            } else if (arr[mid] < data) {
                min = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

Я надеюсь, что благодаря сегодняшней статье читатели смогут правильно написать код на собеседовании, ведь у многих небольших компаний метод бинарного поиска появится в их письменных тестовых вопросах.

Категории