Бинарный поиск в последовательных данных без повторов

Question

Я рассматриваю следующую проблему,

Учитывая отсортированный массив размера n, содержащий целые числа без дубликатов, можем ли мы добиться большего успеха, чем обычный двоичный поиск, используя свойство, которое

• a) нет дубликатов
• b) между двумя смежными целыми числами нет целых чисел (т. е. после 50 либо есть 51, либо 51 нет в массиве)

Идея в том, что когда вы встречаете значение, вы добавляете тест, чтобы увидеть, является ли искомое значение смежным с текущим значением (+ или -1), если да, то интервал поиска вместо того, чтобы делиться пополам, уменьшается до одной точки, индекса рядом с текущей серединой.

Например, предположим, что у вас есть массив tab [i] = i для всех индексов и со всеми значениями от 0 до 99. Мы ищем 51, первая середина равна 50, поэтому нормальный бинарный поиск в худшем случае в 7 попаданиях (log2 (100)). С помощью дополнительного теста мы тестируем 50 и сокращаем интервал поиска до соседа 50, так что конечное значение sh за два шага (но с добавленным тестом).

Это один пример, но он не является репрезентативным моего набора данных, другой пример может быть {0,13223,13225,42341,42342} или любой набор значений, отсортированных без повторов. Просто чтобы дать некоторый контекст, эти массивы, которыми я манипулирую, являются ключами (непустыми индексами) в реализации разреженного массива.

В худшем случае кажется, что мы заканчиваем, когда интервал равен размеру 3, а не 2, так что log2 (n) -1 тестирует.

В коде это даст что-то вроде (Java используется здесь), вызов с 0 в качестве lo и длиной массива-1 в качестве hi для поиска во всем массиве:

// This is Arrays.binarySearch(), but doesn't do any argument validation.
    static int binarySearchGT(int[] array, int value, int lo, int hi) {
        while (lo <= hi) {
            final int mid = (lo + hi) >>> 1;
            final int midVal = array[mid];
            if (midVal < value) {
                lo = mid + 1;
            } else if (midVal > value) {
                hi = mid - 1;
            } else {
                return mid;  // value found
            }
        }
        return ~lo;  // value not present
    }

становится

    static int binarySearch(int[] array, int value, int lo, int hi) {
        while (lo <= hi) {
            final int mid = (lo + hi) >>> 1;
            final int midVal = array[mid];
            if (midVal < value) {
                if (hi != mid && midVal == value -1) {
                    hi = mid + 1;
                } 
                lo = mid + 1;
            } else if (midVal > value) {
                if (lo != mid && midVal == value + 1) {
                    lo = mid - 1;                       
                }
                hi = mid - 1;
            } else {
                return mid;  // value found
            }
        }
        return ~lo;  // value not present
    }

Верны ли мои рассуждения, полагая, что это должно (всегда) быть лучше, чем обычный двоичный поиск в этом конкретном дискретном / неповторяющемся случае входов? Я вижу, что у меня есть дополнительная ветвь и два булевых теста, включая дополнение, но все еще с большими входами, можете ли вы показать случай, когда эта стратегия явно худшая?

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

[Отредактировано, чтобы лучше объяснить, не все элементы присутствуют]

Answer 1

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

Answer 2

Итак, бинарный поиск: причина, по которой мы получаем ~log2(n), ищет данную последовательность в том, что мы разбиваем последовательность на 2 группы в каждой рекурсии, поэтому мы достигаем глубины дерева log2 (n). Скажем, у нас есть упорядоченная последовательность чисел [0,63] в виде набора, тогда наши разбиения, чтобы найти 39, выглядят следующим образом:

Обычный двоичный поиск

value = 39
Step 1: [0,63], split at 32
Step 2: [32-63], split at 48
Step 3: [32-47], split at 40
Step 4: [32-39], split at 36
Step 5: [36-39], split at 38
Step 6: [38-39], split at 39
Step 7: Found 39

Ваш алгоритм

value = 39
Step 1: [0,63], split at 32
Step 2: [32-63], split at 48
Step 3: [32-47], split at 40
Step 4: [32-39], split at 36
Step 5: [36-39], split at 38
Step 6: Found 39

Как вы можете видеть, все, что мы сделали, это понизили максимальную глубину дерева на 1 в худшем случае, но мы увеличили количество тестов на глубину в 2 раза. Ваш алгоритм требует 12 тестов, чтобы найти значение, в то время как традиционный бинарный поиск требует только 7. В конечном счете, сложность по времени все еще равна O(log(n)), но коэффициенты хуже. В любой ситуации производительность в худшем случае здесь хуже, чем при традиционном бинарном поиске.

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