Algoritmo de búsqueda binaria bit a bit

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:

1. 76 = 64 + 8 + 4
2. 10 = 8 + 2
3. 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++ 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 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);
    }
}

# 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# 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

<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 ³¹ – 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.