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 program
function binarySearch ( arr , l , r , x ) { if ( r >= l ) { let mid = l + Math . floor ( ( 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 ) { let l = 0 , h = 1 ; let val = arr [ 0 ] ; while ( val < key ) { l = h ; h = 2 * h ; val = arr [ h ] ; } return binarySearch ( arr , l , h , key ) ; } let arr = [ 3 , 5 , 7 , 9 , 10 , 90 , 100 , 130 , 140 , 160 , 170 ] ; let ans = findPos ( arr , 10 ) ; if ( ans == - 1 ) document . write ( " " ) ; else document . write ( " " + ans ) ;