Meta Binary Search | One | C # implementation of above approach ; Function to show the working of Meta binary search ; int lg = 0 ; Set number of bits to represent largest array index ; This is redundant and will cause error 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
using System ; using System . Collections . Generic ; class GFG { static int bsearch ( List < int > A , int key_to_search ) { int n = ( int ) A . Count ; int lg = ( int ) Math . Log ( n - 1 , 2.0 ) + 1 ; int pos = 0 ; for ( int i = lg - 1 ; i >= 0 ; i -- ) { if ( A [ pos ] == key_to_search ) { return pos ; } int 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 ) ; } static public void Main ( ) { List < int > A = new List < int > ( ) ; int [ ] arr = { - 2 , 10 , 100 , 250 , 32315 } ; for ( int i = 0 ; i < arr . Length ; i ++ ) { A . Add ( arr [ i ] ) ; } Console . WriteLine ( bsearch ( A , 10 ) ) ; } }