Exponential Search | Returns position of first occurrence of x in array ; If x is present at first location itself ; Find range for binary search by repeated doubling ; Call binary search for the found range . ; A recursive binary search function . It returns location of x in given array arr [ l . . r ] is present , otherwise - 1 ; If the element is present at the middle itself ; If element is smaller than mid , then it can only be present n left subarray ; Else the element can only be present in right subarray ; We reach here when element is not present in array ; Driver Code
function exponentialSearch ( arr , n , x ) { if ( arr [ 0 ] == x ) return 0 ; let i = 1 ; while ( i < n && arr [ i ] <= x ) i = i * 2 ; return binarySearch ( arr , i / 2 , Math . min ( i , n - 1 ) , x ) ; } function binarySearch ( arr , l , r , x ) { if ( r >= l ) { let 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 ; } let arr = [ 2 , 3 , 4 , 10 , 40 ] ; let n = arr . length ; let x = 10 ; let result = exponentialSearch ( arr , n , x ) ; if ( result == - 1 ) document . write ( " " ) ; else document . write ( " " + result ) ;