Búsqueda binaria uniforme

La búsqueda binaria uniforme es una optimización del algoritmo de búsqueda binaria cuando se realizan muchas búsquedas en la misma array o en muchas arrays del mismo tamaño. En la búsqueda binaria normal, hacemos operaciones aritméticas para encontrar los puntos medios. Aquí precalculamos los puntos medios y los llenamos en la tabla de búsqueda. La búsqueda de array generalmente funciona más rápido que la aritmética (suma y desplazamiento) para encontrar el punto medio. 

Ejemplos: 

Input : array={1, 3, 5, 6, 7, 8, 9}, v=3
Output : Position of 3 in array = 2

Input :array={1, 3, 5, 6, 7, 8, 9}, v=7
Output :Position of 7 in array = 5

El algoritmo es muy similar al algoritmo de búsqueda binaria . La única diferencia es que se crea una tabla de búsqueda para una array y la tabla de búsqueda se usa para modificar el índice del puntero en la array, lo que hace que la búsqueda sea más rápida. En lugar de mantener un límite inferior y superior, el algoritmo mantiene un índice y el índice se modifica utilizando la tabla de búsqueda. 

// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
 
const int MAX_SIZE = 1000;
 
// lookup table
int lookup_table[MAX_SIZE];
 
// create the lookup table
// for an array of length n
void create_table(int n)
{
    // power and count variable
    int pow = 1;
    int co = 0;
    do {
        // multiply by 2
        pow <<= 1;
 
        // initialize the lookup table
        lookup_table[co] = (n + (pow >> 1)) / pow;
    } while (lookup_table[co++] != 0);
}
 
// binary search
int binary(int arr[], int v)
{
    // mid point of the array
    int index = lookup_table[0] - 1;
 
    // count
    int co = 0;
 
    while (lookup_table[co] != 0) {
 
        // if the value is found
        if (v == arr[index])
            return index;
 
        // if value is less than the mid value
        else if (v < arr[index])
            index -= lookup_table[++co];
 
        // if value is greater than the mid value
        else
            index += lookup_table[++co];
    }
  return index;
}
 
// main function
int main()
{
 
    int arr[] = { 1, 3, 5, 6, 7, 8, 9 };
    int n = sizeof(arr) / sizeof(int);
 
    // create the lookup table
    create_table(n);
 
    // print the position of the array
    cout << "Position of 3 in array = "
         << binary(arr, 3) << endl;
 
    return 0;
}

// Java implementation of above approach
class GFG
{
     
    static int MAX_SIZE = 1000;
     
    // lookup table
    static int lookup_table[] = new int[MAX_SIZE];
     
    // create the lookup table
    // for an array of length n
    static void create_table(int n)
    {
        // power and count variable
        int pow = 1;
        int co = 0;
        do
        {
            // multiply by 2
            pow <<= 1;
     
            // initialize the lookup table
            lookup_table[co] = (n + (pow >> 1)) / pow;
        } while (lookup_table[co++] != 0);
    }
     
    // binary search
    static int binary(int arr[], int v)
    {
        // mid point of the array
        int index = lookup_table[0] - 1;
     
        // count
        int co = 0;
     
        while (lookup_table[co] != 0)
        {
     
            // if the value is found
            if (v == arr[index])
                return index;
     
            // if value is less than the mid value
            else if (v < arr[index])
            {
                index -= lookup_table[++co];
   
            }
             
            // if value is greater than the mid value
            else
            {
                index += lookup_table[++co];
                
            }
        }
        return index ;
    }
     
    // Driver code
    public static void main (String[] args)
    {
     
        int arr[] = { 1, 3, 5, 6, 7, 8, 9 };
        int n = arr.length;
     
        // create the lookup table
        create_table(n);
     
        // print the position of the array
        System.out.println( "Position of 3 in array = " +
                                    binary(arr, 3)) ;
     
     
    }
}
 
// This code is contributed by Ryuga

# Python3 implementation of above approach
 
MAX_SIZE = 1000
 
# lookup table
lookup_table = [0] * MAX_SIZE
 
# create the lookup table
# for an array of length n
def create_table(n):
     
    # power and count variable
    pow = 1
    co = 0
    while True:
         
        # multiply by 2
        pow <<= 1
 
        # initialize the lookup table
        lookup_table[co] = (n + (pow >> 1)) // pow
        if lookup_table[co] == 0:
            break
        co += 1
 
# binary search
def binary(arr, v):
     
    # mid point of the array
    index = lookup_table[0] - 1
 
    # count
    co = 0
 
    while lookup_table[co] != 0:
 
        # if the value is found
        if v == arr[index]:
            return index
 
        # if value is less than the mid value
        elif v < arr[index]:
            co += 1
            index -= lookup_table[co]
 
        # if value is greater than the mid value
        else:
            co += 1
            index += lookup_table[co]
 
# main function
arr = [1, 3, 5, 6, 7, 8, 9]
n = len(arr)
 
# create the lookup table
create_table(n)
 
# print the position of the array
print("Position of 3 in array = ", binary(arr, 3))
 
# This code is contributed by divyamohan123

// C# implementation of above approach
using System;
     
class GFG
{
     
    static int MAX_SIZE = 1000;
     
    // lookup table
    static int []lookup_table = new int[MAX_SIZE];
     
    // create the lookup table
    // for an array of length n
    static void create_table(int n)
    {
        // power and count variable
        int pow = 1;
        int co = 0;
        do
        {
            // multiply by 2
            pow <<= 1;
     
            // initialize the lookup table
            lookup_table[co] = (n + (pow >> 1)) / pow;
        } while (lookup_table[co++] != 0);
    }
     
    // binary search
    static int binary(int []arr, int v)
    {
        // mid point of the array
        int index = lookup_table[0] - 1;
     
        // count
        int co = 0;
     
        while (lookup_table[co] != 0)
        {
     
            // if the value is found
            if (v == arr[index])
                return index;
     
            // if value is less than the mid value
            else if (v < arr[index])
            {
                index -= lookup_table[++co];
                return index;
            }
             
            // if value is greater than the mid value
            else
            {
                index += lookup_table[++co];
                return index;
            }
        }
        return index ;
    }
     
    // Driver code
    public static void Main ()
    {
     
        int []arr = { 1, 3, 5, 6, 7, 8, 9 };
        int n = arr.GetLength(0);
     
        // create the lookup table
        create_table(n);
     
        // print the position of the array
    Console.WriteLine( "Position of 3 in array = " +
                                    binary(arr, 3)) ;
     
     
    }
}
 
/* This code contributed by PrinciRaj1992 */

<script>
 
// Javascript implementation of above approach
let MAX_SIZE = 1000;
   
// lookup table
let lookup_table = new Array(MAX_SIZE);
lookup_table.fill(0);
   
// Create the lookup table
// for an array of length n
function create_table(n)
{
     
    // Power and count variable
    let pow = 1;
    let co = 0;
     
    while(true)
    {
         
        // Multiply by 2
        pow <<= 1;
   
        // Initialize the lookup table
        lookup_table[co] = parseInt((n + (pow >> 1)) /
                                          pow, 10);
         
        if (lookup_table[co++] == 0)
        {
            break;
        }
    }
}
   
// Binary search
function binary(arr, v)
{
     
    // mid point of the array
    let index = lookup_table[0] - 1;
   
    // count
    let co = 0;
   
    while (lookup_table[co] != 0)
    {
         
        // If the value is found
        if (v == arr[index])
            return index;
   
        // If value is less than the mid value
        else if (v < arr[index])
        {
            index -= lookup_table[++co];
            return index;
        }
           
        // If value is greater than the mid value
        else
        {
            index += lookup_table[++co];
            return index;
        }
    }
    return index ;
}
 
// Driver code
let arr = [ 1, 3, 5, 6, 7, 8, 9 ];
let n = arr.length;
 
// Create the lookup table
create_table(n);
 
// Print the position of the array
document.write("Position of 3 in array = " +
               binary(arr, 3));
                
// This code is contributed by divyeshrabadiya07
 
</script>

Position of 3 in array = 1

Referencias: https://en.wikipedia.org/wiki/Uniform_binary_search