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