Вы действительно используете бинарный поиск?

Redis задняя часть Байду LeetCode

Действительно ли бинарный поиск легко написать? не обязательно!

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

 /**
     * 二分查找
     * @param a  源数组 注意这个数组的值一定是经过排序的有序数组
     * @param n  数组大小
     * @param key 想要查找位置的值
     * @return
     */
    public int search(int[] a, int n, int key) {
        int low = 0;
        int high = n - 1;

        while (low <= high) {
            //这个地方 计算mid的值 有可能会发生 越界异常的，low+high 非常有可能超过int的最大值限制
            //所以这边可以优化成low+(high-low)/2  甚至用到位运算low+((high-low)>>1)
            int mid = (low + high) / 2;
            if (a[mid] == key) {
                return mid;
            } else if (a[mid] < key) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }

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

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

Этот вид бинарного поиска более сложен для написания и подвержен ошибкам Заинтересованные студенты могут перейти на leetcode, чтобы написать и поиграть.

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

Сделайте больше, потому что эти 2 типа имеют дополнительные преимущества для точного поиска (хотя эти 2 требуют дополнительного места в памяти).

Когда уместно использовать бинарный поиск?

Первое, что нужно отметить, это то, что скорость бинарного поиска довольно высокая, не думайте, что он не быстрый, потому что он прост в написании. . Это не так просто, как писать и работать очень медленно. Пузырьковая сортировка — это две разные вещи. В конце концов, скорость O (logn), даже если у вас есть 2 в 32-й степени примерно 4 миллиарда данных для проверки данных, вы можете проверить их не более 32 раз.

Но у бинарного поиска есть свои ограничения:

  1. Двоичный поиск требует, чтобы источником данных был массивПредположим, мы используем бинарный поиск, где связанный список является структурой данных, подумайте о длине произвольного доступа к связанному списку. Сложность O(n). Мы можем восстановить эту сцену: если предположить, что бинарный поиск используется в связанном списке, то позицию нахождения середины в первый раз нужно переместить n/2 раза, найдено, что позиция середины перемещается n/4 раза во второй раз и так далее для n/8 ,n/16, видно, что этот поиск Сложность времени операции mid составляет O (n), а затем подумайте о других операциях,Фактическое время выполнения должно выглядеть медленнее, чем заказ,Таким образом, бинарный поиск нельзя использовать в связанных списках, только в массивах.

  2. Двоичный поиск должен требовать, чтобы источник данных был упорядоченным, и источник данных предпочтительно был статическим.Большинство сценариев динамических источников данных не используют двоичный поиск. Поскольку бинарный поиск должен требовать, чтобы источник данных был упорядоченным, если наш источник данных не является упорядоченным, он должен быть отсортирован перед поиском. Типа конечно тоже Это отнимает много времени, а самый быстрый — O(nlogn), поэтому, если искомый источник данных часто вставляется и удаляется и его необходимо часто переупорядочивать, используйте бинарный поиск. Это очень медленно.

  3. Не используйте бинарный поиск, когда объем данных слишком велик, и не используйте его, когда объем данных слишком мал, лучше всего использовать его в особых случаях.. Как упоминалось ранее, бинарный поиск следует выполнять с массивом. Структура данных, если объем данных здесь слишком велик, то объем памяти, который вам нужен, слишком велик, например, ваша оставшаяся память составляет 4 ГБ, ваши данные имеют 3,8 ГБ, Тогда велика вероятность, что вам здесь не удастся использовать бинарный поиск, потому что массив требует непрерывного места в памяти, а у нас остается 4гб памяти, что не означает, что оставшееся место в 4гб непрерывное.

Если объем данных слишком мал, почему бы не использовать его? На самом деле, вы не можете его использовать. Основная причина в том, что объем данных слишком мал, преимущество бинарного поиска неочевидно, и хлопотно писать. Если объем данных небольшой, используйте последовательный поиск. Есть особый случай, например, если операция сравнения нашего бинарного поиска занимает много времени, лучше всего использовать бинарный поиск, т. е. Для трудоемкого поиска одной операции сравнения (например, сравнения больших строк длиной более 500 или около того) лучше всего использовать бинарный поиск, потому что бинарный поиск может значительно сократить количество сравнений.

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

В компьютерном мире есть две известные поговорки.1. Любую проблему в информатике можно решить, добавив непрямой промежуточный слой. 2. Если времени недостаточно, используйте место для обмена, Если места недостаточно, используйте время, чтобы заменить его.

Поэтому, если вы хотите реализовать упорядоченный набор бинарного поиска в связанном списке, который не может быть медленным, это хороший способ обменять пространство на время. «Пропустить стол» — очень эффективное решение. Проще говоря, так называемая таблица пропуска состоит в том, чтобы создать n индексных слоев для связанного списка, а затем найти его через индексный слой при поиске. Я нарисовал эскиз, чтобы вы могли его испытать:

Это легко понять, на самом деле упорядоченная коллекция Redis также использует это.Просто решение пропуска таблицы появилось относительно поздно, и многие SDK не имеют реализации пропуска таблицы, а Существует множество реализаций красно-черных деревьев, поэтому о таблице прыжков знают немногие. Из-за наличия индекса таблица пропуска даже быстрее, чем красно-черное дерево, при поиске в интервале.

Конкретную реализацию таблицы пропуска можно узнать у Baidu самостоятельно.Вроде эта ссылка хороша

Вот просто для расширения кругозора и пусть все знают, что такое есть. Заинтересованные студенты могут писать и читать самостоятельно.Стратегии вставки, удаления и обновления индексации таблиц пропуска весьма интересны. с вещами.

Категории