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 approachMAX_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!
