Meta Binary Search | One | Function to show the working of Meta binary search ; Set number of bits to represent ; largest array index This is redundant and will cause error for some case 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
< ? php function bsearch ( $ A , $ key_to_search , $ n ) { $ lg = log ( $ n - 1 , 2 ) + 1 ; $ pos = 0 ; for ( $ i = $ lg - 1 ; $ i >= 0 ; $ i -- ) { if ( $ A [ $ pos ] == $ key_to_search ) return $ pos ; $ new_pos = $ pos | ( 1 << $ i ) ; if ( ( $ new_pos < $ n ) && ( $ A [ $ new_pos ] <= $ key_to_search ) ) $ pos = $ new_pos ; } return ( ( $ A [ $ pos ] == $ key_to_search ) ? $ pos : -1 ) ; } $ A = [ -2 , 10 , 100 , 250 , 32315 ] ; $ ans = bsearch ( $ A , 10 , 5 ) ; echo $ ans ; ? >