Meta Binary Search | One | Function to show the working of Meta binary search ; Set number of bits to represent ; largest array index while ( ( 1 << lg ) < n - 1 ) : lg += 1 ; Incrementally construct the index of the target value ; find the element in one direction and update position ; if element found return pos otherwise - 1 ; Driver code
import math NEW_LINE def bsearch ( A , key_to_search ) : NEW_LINE INDENT n = len ( A ) NEW_LINE lg = int ( math . log2 ( n - 1 ) ) + 1 ; NEW_LINE pos = 0 NEW_LINE for i in range ( lg - 1 , - 1 , - 1 ) : NEW_LINE INDENT if ( A [ pos ] == key_to_search ) : NEW_LINE INDENT return pos NEW_LINE DEDENT new_pos = pos | ( 1 << i ) NEW_LINE if ( ( new_pos < n ) and ( A [ new_pos ] <= key_to_search ) ) : NEW_LINE INDENT pos = new_pos NEW_LINE DEDENT DEDENT return ( pos if ( A [ pos ] == key_to_search ) else - 1 ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT A = [ - 2 , 10 , 100 , 250 , 32315 ] NEW_LINE print ( bsearch ( A , 10 ) ) NEW_LINE DEDENT