Uniform Binary Search | Python3 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
MAX_SIZE = 1000 NEW_LINE lookup_table = [ 0 ] * MAX_SIZE NEW_LINE def create_table ( n ) : NEW_LINE INDENT pow = 1 NEW_LINE co = 0 NEW_LINE while True : NEW_LINE INDENT pow <<= 1 NEW_LINE lookup_table [ co ] = ( n + ( pow >> 1 ) ) // pow NEW_LINE if lookup_table [ co ] == 0 : NEW_LINE INDENT break NEW_LINE DEDENT co += 1 NEW_LINE DEDENT DEDENT def binary ( arr , v ) : NEW_LINE INDENT index = lookup_table [ 0 ] - 1 NEW_LINE co = 0 NEW_LINE while lookup_table [ co ] != 0 : NEW_LINE INDENT if v == arr [ index ] : NEW_LINE INDENT return index NEW_LINE DEDENT elif v < arr [ index ] : NEW_LINE INDENT co += 1 NEW_LINE index -= lookup_table [ co ] NEW_LINE DEDENT else : NEW_LINE INDENT co += 1 NEW_LINE index += lookup_table [ co ] NEW_LINE DEDENT DEDENT DEDENT arr = [ 1 , 3 , 5 , 6 , 7 , 8 , 9 ] NEW_LINE n = len ( arr ) NEW_LINE create_table ( n ) NEW_LINE print ( " Position ▁ of ▁ 3 ▁ in ▁ array ▁ = ▁ " , binary ( arr , 3 ) ) NEW_LINE