Uniform Binary Search is an optimization of Binary Search algorithm when many searches are made on same array or many arrays of same size. In normal binary search, we do arithmetic operations to find the mid points. Here we precompute mid points and fills them in lookup table. The array look-up generally works faster than arithmetic done (addition and shift) to find the mid point.Â
Examples:Â
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
The algorithm is very similar to Binary Search algorithm, The only difference is a lookup table is created for an array and the lookup table is used to modify the index of the pointer in the array which makes the search faster . Instead of maintaining lower and upper bound the algorithm maintains an index and the index is modified using the lookup table.Â
C++
// C++ implementation of above approach#include <bits/stdc++.h>using namespace std;Â
const int MAX_SIZE = 1000;Â
// lookup tableint lookup_table[MAX_SIZE];Â
// create the lookup table// for an array of length nvoid 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 searchint 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 functionint 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
// 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
# Python3 implementation of above approachÂ
MAX_SIZE = 1000Â
# lookup tablelookup_table = [0] * MAX_SIZEÂ
# create the lookup table# for an array of length ndef 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 searchdef 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 functionarr = [1, 3, 5, 6, 7, 8, 9]n = len(arr)Â
# create the lookup tablecreate_table(n)Â
# print the position of the arrayprint("Position of 3 in array = ", binary(arr, 3))Â
# This code is contributed by divyamohan123 |
C#
// 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 */ |
Javascript
<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 codelet 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> |
Output:Â
Position of 3 in array = 1
Â
Time Complexity : O(log n).
 Auxiliary Space Complexity : O(log n)Â
References : https://en.wikipedia.org/wiki/Uniform_binary_search
Â
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
