Requisito previo: búsqueda binaria
El algoritmo Bitwise Binary Search es una versión modificada de Binary Search basada en la siguiente idea:
Todo número se puede representar como la suma de las potencias del número 2.
Ejemplos:
- 76 = 64 + 8 + 4
- 10 = 8 + 2
- 7 = 4 + 2 + 1
Acercarse:
- Calcule la primera potencia de 2 que sea mayor o igual que el tamaño de la array.
- Inicializar un índice como 0.
- Haga un bucle mientras la potencia calculada sea mayor que 0 y cada vez divídalo por 2.
- Cada vez que el elemento en la posición [índice + potencia] <= objetivo, agregamos a la variable de índice el valor de potencia respectivo. (Construir la suma)
- Después de los bucles for, verifique si el elemento en la posición [índice] == destino. Si es así, el elemento de destino está presente en la array, de lo contrario no.
- (no se necesita división solo adición y desplazamiento bit a bit)
C++
// C++ program to implement Bitwise Binary Search
#include <iostream>
using namespace std;
int binary_search(int* arr, int size, int target)
{
int index, power;
// Compute the first power of 2 that is >= size
for (power = 1; power < size; power <<= 1)
;
// loop while(power > 0)
// and divide power by two each iteration
for (index = 0; power; power >>= 1) {
// if the next condition is true
// it means that the power value can contribute to
// the "sum"(a closer index where target might be)
if (index + power < size
&& arr[index + power] <= target)
index += power;
}
// if the element at position [index] == target,
// the target value is present in the array
if (arr[index] == target)
return index;
// else the value is not present in the array
return -1;
}
int main()
{
int arr[5] = { 1, 3, 5, 7, 8 };
int size = 5;
int x = 3;
int answer = binary_search(arr, size, x);
if (answer == -1)
cout << "Element not found";
else
cout << "Element found at position " << answer;
// This code is contributed
// by Gatea David
}
Java
// Java program to implement Bitwise Binary Search
import java.util.*;
class GFG {
static int binary_search(int[] arr, int size,
int target)
{
int index, power;
// Compute the first power of 2 that is >= size
for (power = 1; power < size; power <<= 1)
;
// loop while(power > 0)
// and divide power by two each iteration
for (index = 0; power > 0; power >>= 1) {
// if the next condition is true
// it means that the power value can
// contribute to the "sum"(a closer index where
// target might be)
if (index + power < size
&& arr[index + power] <= target)
index += power;
}
// if the element at position [index] == target,
// the target value is present in the array
if (arr[index] == target)
return index;
// else the value is not present in the array
return -1;
}
// Driver code
public static void main(String[] args)
{
int[] arr = { 1, 3, 5, 7, 8 };
int size = 5;
int x = 3;
int answer = binary_search(arr, size, x);
if (answer == -1)
System.out.print("Element not found");
else
System.out.print("Element found at position "
+ answer);
}
}
Python3
# Python code for the above approach
def binary_search(arr, size, target):
# Compute the first power of 2 that is >= size
power = 1
while(power < size):
power = power << 1
# loop while(power > 0)
# and divide power by two each iteration
power = 1
index = 0
while(power):
# if the next condition is true
# it means that the power value can contribute to
# the "sum"(a closer index where target might be)
if (index + power < size and arr[index + power] <= target):
index += power
power >>= 1
# if the element at position [index] == target,
# the target value is present in the array
if (arr[index] == target):
return index
# else the value is not present in the array
return -1
arr = [1, 3, 5, 7, 8]
size = 5
x = 3
answer = binary_search(arr, size, x)
if (answer == -1):
print("Element not found")
else:
print(f"Element found at position {answer}")
# This code is contributed by gfgking
C#
// C# program to implement Bitwise Binary Search
using System;
class GFG {
static int binary_search(int[] arr, int size,
int target)
{
int index, power;
// Compute the first power of 2 that is >= size
for (power = 1; power < size; power <<= 1)
;
// loop while(power > 0)
// and divide power by two each iteration
for (index = 0; power != 0; power >>= 1) {
// if the next condition is true
// it means that the power value can contribute
// to the "sum"(a closer index where target
// might be)
if (index + power < size
&& arr[index + power] <= target)
index += power;
}
// if the element at position [index] == target,
// the target value is present in the array
if (arr[index] == target)
return index;
// else the value is not present in the array
return -1;
}
public static int Main()
{
int[] arr = new int[] { 1, 3, 5, 7, 8 };
int size = 5;
int x = 3;
int answer = binary_search(arr, size, x);
if (answer == -1)
Console.Write("Element not found");
else
Console.Write("Element found at position "
+ answer);
return 0;
}
}
// This code is contributed by Taranpreet
Javascript
<script>
// JavaScript code for the above approach
function binary_search(arr, size, target)
{
let index, power;
// Compute the first power of 2 that is >= size
for (power = 1; power < size; power <<= 1)
;
// loop while(power > 0)
// and divide power by two each iteration
for (index = 0; power; power >>= 1) {
// if the next condition is true
// it means that the power value can contribute to
// the "sum"(a closer index where target might be)
if (index + power < size
&& arr[index + power] <= target)
index += power;
}
// if the element at position [index] == target,
// the target value is present in the array
if (arr[index] == target)
return index;
// else the value is not present in the array
return -1;
}
let arr = [1, 3, 5, 7, 8];
let size = 5;
let x = 3;
let answer = binary_search(arr, size, x);
if (answer == -1)
document.write("Element not found");
else
document.write("Element found at position " + answer);
// This code is contributed by Potta Lokesh
</script>
Element found at position 1
Complejidad del tiempo: 
La complejidad temporal de la búsqueda binaria se puede escribir como:
T(n) = T(n/2) + c
La recurrencia anterior se puede resolver mediante el método del árbol de recurrencia o el método maestro. Cae en el caso II del Método Maestro y la solución de la recurrencia es
Espacio auxiliar: O(1) en caso de implementación iterativa. En el caso de una implementación recursiva, O(Logn) espacio de pila de llamadas recursivas.
Paradigma algorítmico: disminuir y conquistar .
Nota:
Aquí estamos usando
int mid = bajo + (alto – bajo)/2;
Tal vez se pregunte por qué estamos calculando el índice medio de esta manera, simplemente podemos sumar el índice inferior y superior y dividirlo por 2.
int mid = (bajo + alto)/2;
Pero si calculamos el índice medio así, significa que nuestro código no es 100% correcto, contiene errores.
Es decir, falla para valores más grandes de variables int bajas y altas. Específicamente, falla si la suma de alto y bajo es mayor que el valor int positivo máximo (2 31 – 1).
La suma se desborda a un valor negativo y el valor se mantiene negativo cuando se divide por 2. En java, lanza ArrayIndexOutOfBoundException.
int mid = bajo + (alto – bajo)/2;
Así que es mejor usarlo así. Este error se aplica igualmente a la combinación de clasificación y otros algoritmos de dividir y conquistar.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA