Meta Binary Search | One | Java implementation of above approach ; 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 java . util . Vector ; import com . google . common . math . BigIntegerMath ; import java . math . * ; class GFG { static int bsearch ( Vector < Integer > A , int key_to_search ) { int n = ( int ) A . size ( ) ; int lg = BigIntegerMath . log2 ( BigInteger . valueOf ( n - 1 ) , RoundingMode . UNNECESSARY ) + 1 ; int pos = 0 ; for ( int i = lg - 1 ; i >= 0 ; i -- ) { if ( A . get ( pos ) == key_to_search ) { return pos ; } int new_pos = pos | ( 1 << i ) ; if ( ( new_pos < n ) && ( A . get ( new_pos ) <= key_to_search ) ) { pos = new_pos ; } } return ( ( A . get ( pos ) == key_to_search ) ? pos : - 1 ) ; } static public void main ( String [ ] args ) { Vector < Integer > A = new Vector < Integer > ( ) ; int [ ] arr = { - 2 , 10 , 100 , 250 , 32315 } ; for ( int i = 0 ; i < arr . length ; i ++ ) { A . add ( arr [ i ] ) ; } System . out . println ( bsearch ( A , 10 ) ) ; } }