Алгоритм побитового бинарного поиска

Предварительное условие: бинарный поиск

Алгоритм побитового бинарного поиска представляет собой модифицированную версию бинарного поиска, основанную на следующей идее:

Every number can be represented as a sum of the powers of the number 2.

Examples:

1. 76 = 64 + 8 + 4
2. 10 = 8  + 2
3. 7 = 4 + 2 + 1

Подход:

• Вычислите первую степень числа 2, которая больше или равна размеру массива.
• Инициализировать индекс как 0.
• Цикл, пока вычисленная мощность больше 0, и каждый раз делите ее на 2.
• Каждый раз, когда элемент в позиции [index + power] <= target, мы добавляем к переменной index соответствующее значение мощности. (Построить сумму)
• После цикла for проверьте, является ли элемент в позиции [index] == target. Если это так, целевой элемент присутствует в массиве, иначе нет.
• (деление не требуется, только сложение и побитовый сдвиг)

Сложность времени:

Временная сложность бинарного поиска может быть записана как:

T(n) = T(n/2) + c

Вышеупомянутое повторение может быть решено либо с помощью метода дерева повторения, либо с помощью основного метода. Он падает в случае II Мастер-метода, и решение повторяемости

Вспомогательное пространство: O(1) в случае итеративной реализации. В случае рекурсивной реализации O(Logn) пространства стека рекурсивных вызовов.

Алгоритмическая парадигма: уменьшай и властвуй.

Примечание:

Здесь мы используем

int mid = low + (high – low)/2;

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

int mid = (low + high)/2;

Но если мы посчитаем такой средний индекс означает, что наш код не на 100% правильный, он содержит ошибки.

То есть он не работает для больших значений переменных int low и high. В частности, он терпит неудачу, если сумма low и high больше, чем максимальное положительное значение int(2 ³¹ – 1 ).

Сумма переполняется до отрицательного значения, и значение остается отрицательным при делении на 2. В java вызывается исключение ArrayIndexOutOfBoundException.

int mid = low + (high – low)/2;

Так что лучше использовать так. Эта ошибка в равной степени относится к сортировке слиянием и другим алгоритмам «разделяй и властвуй».