Algoritmo de búsqueda binaria modificada de base N

La búsqueda binaria modificada de N-Base es un algoritmo basado en bases numéricas que se puede usar para encontrar un elemento en una array ordenada arr[]. Este algoritmo es una extensión de la búsqueda binaria Bitwise y tiene un tiempo de ejecución similar.

Ejemplos: 

Entrada: arr[] = {0, 1, 4, 5, 8, 11, 15, 21, 45, 70, 100}, target = 45
Salida: 7
Explicación: El valor 45 está presente en el índice 7

Entrada: arr[] = {1, 6, 8, 10}, target = 9
Salida: -1
Explicación: El valor 9 no está presente en la array dada.

Intuición: todos los números de un sistema numérico se pueden expresar en otro sistema numérico que tenga cualquier número (por ejemplo, 2, 3, 7) como base de ese sistema numérico. Por ejemplo, el 7 del sistema numérico decimal se puede expresar como (21) ₃ en un sistema numérico que tiene como base 3 . Por lo tanto, el concepto de búsqueda binaria bit a bit se puede implementar utilizando cualquier número N como base de un sistema numérico.

Enfoque: El índice del elemento de destino se busca sumando potencias de base (cualquier número entero positivo a partir de 2) a una suma (inicialmente 0). Cuando se encuentra tal potencia, se hace un cálculo para contar el número de veces que se puede usar para encontrar el índice objetivo, y ese valor se suma a la suma. La parte de contar cuántas veces se puede usar una potencia es similar a la «búsqueda binaria bit a bit» del artículo de búsqueda binaria .

1. Defina un número base y una potencia de dos mayor o igual a la base (la potencia de dos ayudará a contar cuántas veces se puede agregar una potencia de base al índice final, de manera eficiente)
2. Calcule la primera potencia de la base (N) que es mayor que el tamaño del arreglo. ( N ^k donde k es un número entero mayor o igual a uno y X ^k es la primera potencia de base mayor o igual al tamaño del arreglo).
3. Inicialice un índice (finId) como 0 que almacenará la posición final donde debería estar el elemento de destino al final de todas las iteraciones.
4. Haga un bucle mientras la potencia calculada sea mayor que 0 y cada vez divídalo por el valor base.
   1. Verifique cuántas veces se puede usar este poder y agregue ese valor al finId.
   2. Para verificar esto, use las condiciones mencionadas a continuación:

• finId + poder de la base < tamaño de la array (M)
• valor en finId + poder de base ≤ objetivo

Mientras la iteración está completa, verifique si el valor en el índice final es el mismo que el objetivo o no. Si no es así, entonces el valor no está presente en la array.

Ilustración: Consulte la ilustración a continuación para una mejor comprensión.

Ilustración: arr[] = {1, 4, 5, 8, 11, 15, 21, 45, 70, 100}, tamaño de array (M) = 10, objetivo = 45, base (N) = 3

Pasos:

1. Calcule la primera potencia ( potencia ) de 3 ( Base ) mayor que 10 (M), potencia = 27 en este caso.
2. Inicialice un índice final ( finId ) como 0 (posición en arr[] donde el valor objetivo debe estar al final).
3. Ahora iterar a través de las potencias de 3 ( Base ) que son menores o iguales a 27 y agregarlas al índice como sigue:
   1. Primera iteración: finId = 0. power es 27 y no se puede usar porque finId + power > M. Entonces, finId = 0 .
   2. 2da iteración: f inId = 0. power es 9 y no se puede usar porque el elemento en finId + power > target 
      es decir, arr[finId + power] > target. Así que finId = 0 .
   3. 3ra iteración: f inId = 0. power es 3, esta vez se puede usar power porque arr[finId + power] < target. Ahora cuente cuántas veces se puede sumar 3 para encontrar. En este caso 3 puede sumar dos veces. fi nId después de la tercera iteración será 6 (finId += 3 + 3). 3 no se puede agregar más de 2 veces porque finId pasará el índice donde está el valor objetivo. Así que finId = 0 + 3 + 3 = 6 .
   4. Cuarta iteración: f inId = 6. power es 1, power se puede usar porque arr[finId + power] ≤ target(45). Nuevamente cuente cuántas veces se puede usar 1 . En este caso, 1 solo se puede usar una vez. Entonces agregue 1 solo una vez con finId. Entonces, finId = 6+1 = 7 .
4. después de la cuarta iteración, la potencia es 0, así que salga del bucle.
5. arr[7] = destino. Entonces el valor se encuentra en el índice 7.

Notas:

1. En cada iteración, la potencia se puede usar como máximo (Base – 1) veces
2. La base puede ser cualquier número entero positivo a partir de 2
3. La array debe ordenarse para realizar este algoritmo de búsqueda

A continuación se muestra la implementación del enfoque anterior (en comparación con un algoritmo de búsqueda binario clásico):

// C++ code to implement the above approach
#include<bits/stdc++.h>
using namespace std;
  
#define N 3
#define PowerOf2 4
  
int Numeric_Base_Search(int arr[], int M, 
                        int target){
    unsigned long long i, step1, 
    step2 = PowerOf2, times;
  
    // Find the first power of N 
    // greater than the array size
    for (step1 = 1; step1 < M; step1 *= N);
      
    for (i = 0; step1; step1 /= N)
  
        // Each time a power can be used
        // count how many times 
        // it can be used
        if (i + step1 < M && arr[i + step1] 
            <= target){
            for (times = 1; step2; 
                 step2 >>= 1)
                if (i + 
                    (step1 * (times + step2)) 
                    < M && 
                    arr[i + 
                      (step1 * (times + step2))] 
                    <= target)
                    times += step2;
  
            step2 = PowerOf2;
  
            // Add to final result 
            // how many times 
            // can the power be used
            i += times * step1;
        }
  
    // Return the index 
    // if the element is present in array
    // else return -1
    return arr[i] == target ? i : -1;
}
  
// Driver code
int main(){
    int arr[10] = 
    {1, 4, 5, 8, 11, 15, 21, 45, 70, 100};
    int target = 45, M = 10;
    int answer  = Numeric_Base_Search(arr, M, target);
    cout<<answer;
    return 0;
}

// Java code to implement the above approach
class GFG {
  
    static int N = 3;
    static int PowerOf2 = 4;
  
    static int Numeric_Base_Search(int[] arr, int M,
                                   int target)
    {
        int i, step1, step2 = PowerOf2, times;
  
        // Find the first power of N
        // greater than the array size
        for (step1 = 1; step1 < M; step1 *= N)
            ;
  
        for (i = 0; step1 > 0; step1 /= N) {
  
            // Each time a power can be used
            // count how many times
            // it can be used
            if (i + step1 < M && arr[i + step1] <= target) {
                for (times = 1; step2 > 0; step2 >>= 1)
                    if (i + (step1 * (times + step2)) < M
                        && arr[i
                               + (step1 * (times + step2))]
                               <= target)
                        times += step2;
  
                step2 = PowerOf2;
  
                // Add to final result
                // how many times
                // can the power be used
                i += times * step1;
            }
        }
        
        // Return the index
        // if the element is present in array
        // else return -1
        return arr[i] == target ? i : -1;
    }
  
    // Driver code
    public static void main(String args[])
    {
        int[] arr = { 1, 4, 5, 8, 11, 15, 21, 45, 70, 100 };
        int target = 45, M = 10;
        int answer = Numeric_Base_Search(arr, M, target);
        System.out.println(answer);
    }
}
  
// This code is contributed by Saurabh Jaiswal

# Python code for the above approach
N = 3
PowerOf2 = 4
  
def Numeric_Base_Search(arr, M, target):
    i = None
    step1 = None
    step2 = PowerOf2
    times = None
  
    # Find the first power of N
    # greater than the array size
    step1 = 1
    while(step1 < M):
        step1 *= N
  
    i = 0
    while(step1):
        step1 = step1 // N
  
        # Each time a power can be used
        # count how many times
        # it can be used
        if (i + step1 < M and arr[i + step1] <= target):
            times=1
            while(step2):
                step2 >>= 1
                if (i + (step1 * (times + step2)) < M and arr[i + (step1 * (times + step2))] <= target):
                    times += step2;
  
            step2 = PowerOf2;
  
            # Add to final result
            # how many times
            # can the power be used
            i += times * step1
  
    # Return the index
    # if the element is present in array
    # else return -1
    return i if arr[i] == target else -1
  
   # Driver code
arr = [1, 4, 5, 8, 11, 15, 21, 45, 70, 100]
target = 45
M = 10
answer = Numeric_Base_Search(arr, M, target)
print(answer)
  
  # This code is contributed by Saurabh Jaiswal

// C# code to implement the above approach
using System;
class GFG {
  
    static int N = 3;
    static int PowerOf2 = 4;
  
    static int Numeric_Base_Search(int[] arr, int M,
                                   int target)
    {
        int i, step1, step2 = PowerOf2, times;
  
        // Find the first power of N
        // greater than the array size
        for (step1 = 1; step1 < M; step1 *= N)
            ;
  
        for (i = 0; step1 > 0; step1 /= N) {
  
            // Each time a power can be used
            // count how many times
            // it can be used
            if (i + step1 < M && arr[i + step1] <= target) {
                for (times = 1; step2 > 0; step2 >>= 1)
                    if (i + (step1 * (times + step2)) < M
                        && arr[i
                               + (step1 * (times + step2))]
                               <= target)
                        times += step2;
  
                step2 = PowerOf2;
  
                // Add to final result
                // how many times
                // can the power be used
                i += times * step1;
            }
        }
        // Return the index
        // if the element is present in array
        // else return -1
        return arr[i] == target ? i : -1;
    }
  
    // Driver code
    public static void Main()
    {
        int[] arr = { 1, 4, 5, 8, 11, 15, 21, 45, 70, 100 };
        int target = 45, M = 10;
        int answer = Numeric_Base_Search(arr, M, target);
        Console.WriteLine(answer);
    }
}
  
// This code is contributed by ukasp.

<script>
    // JavaScript code for the above approach
    let N = 3
    let PowerOf2 = 4
  
    function Numeric_Base_Search(arr, M,
      target) {
      let i, step1,
        step2 = PowerOf2, times;
  
      // Find the first power of N 
      // greater than the array size
      for (step1 = 1; step1 < M; step1 *= N);
  
      for (i = 0; step1; step1 /= N)
  
        // Each time a power can be used
        // count how many times 
        // it can be used
        if (i + step1 < M && arr[i + step1]
          <= target) {
          for (times = 1; step2;
            step2 >>= 1)
            if (i +
              (step1 * (times + step2))
              < M &&
              arr[i +
              (step1 * (times + step2))]
              <= target)
              times += step2;
  
          step2 = PowerOf2;
  
          // Add to final result 
          // how many times 
          // can the power be used
          i += times * step1;
        }
  
      // Return the index 
      // if the element is present in array
      // else return -1
      return arr[i] == target ? i : -1;
    }
  
    // Driver code
    let arr =
      [1, 4, 5, 8, 11, 15, 21, 45, 70, 100];
    let target = 45, M = 10;
    let answer = Numeric_Base_Search(arr, M, target);
    document.write(answer);
  
  // This code is contributed by Potta Lokesh
  </script>

7

Complejidad de tiempo: O(log _N M* log ₂ N)
Espacio auxiliar: O(1)