Find position of an element in a sorted array of infinite numbers | Simple binary search algorithm ; function takes an infinite size array and a key to be searched and returns its position if found else - 1. We don 't know size of arr[] and we can assume size to be infinite in this function. NOTE THAT THIS FUNCTION ASSUMES arr[] TO BE OF INFINITE SIZE THEREFORE, THERE IS NO INDEX OUT OF BOUND CHECKING ; Find h to do binary search ; store previous high ; double high index ; update new val ; at this point we have updated low and high indices , Thus use binary search between them ; Driver Code
< ? php function binarySearch ( $ arr , $ l , $ r , $ x ) { if ( $ r >= $ l ) { $ mid = $ l + ( $ r - $ l ) / 2 ; if ( $ arr [ $ mid ] == $ x ) return $ mid ; if ( $ arr [ $ mid ] > $ x ) return binarySearch ( $ arr , $ l , $ mid - 1 , $ x ) ; return binarySearch ( $ arr , $ mid + 1 , $ r , $ x ) ; } return -1 ; } function findPos ( $ arr , $ key ) { $ l = 0 ; $ h = 1 ; $ val = $ arr [ 0 ] ; while ( $ val < $ key ) { $ l = $ h ; $ h = 2 * $ h ; $ val = $ arr [ $ h ] ; } return binarySearch ( $ arr , $ l , $ h , $ key ) ; } $ arr = array ( 3 , 5 , 7 , 9 , 10 , 90 , 100 , 130 , 140 , 160 , 170 ) ; $ ans = findPos ( $ arr , 10 ) ; if ( $ ans == -1 ) echo " Element ▁ not ▁ found " ; else echo " Element ▁ found ▁ at ▁ index ▁ " , $ ans ; ? >