Exponential Search | Returns the position of first occurrence of x in array ; IF x is present at first location itself ; Find range for binary search j by repeated doubling ; Call binary search for the found range ; A recurssive binary search function returns location of x in given array arr [ l . . r ] is present , otherwise - 1 ; If the element is present at the middle itself ; If the element is smaller than mid , then it can only be present in the left subarray ; Else he element can only be present in the right ; We reach here if the element is not present ; Driver Code
def exponentialSearch ( arr , n , x ) : NEW_LINE INDENT if arr [ 0 ] == x : NEW_LINE INDENT return 0 NEW_LINE DEDENT i = 1 NEW_LINE while i < n and arr [ i ] <= x : NEW_LINE INDENT i = i * 2 NEW_LINE DEDENT return binarySearch ( arr , i / 2 , min ( i , n - 1 ) , x ) NEW_LINE DEDENT def binarySearch ( arr , l , r , x ) : NEW_LINE INDENT if r >= l : NEW_LINE INDENT mid = l + ( r - l ) / 2 NEW_LINE if arr [ mid ] == x : NEW_LINE INDENT return mid NEW_LINE DEDENT if arr [ mid ] > x : NEW_LINE INDENT return binarySearch ( arr , l , mid - 1 , x ) NEW_LINE DEDENT return binarySearch ( arr , mid + 1 , r , x ) NEW_LINE DEDENT return - 1 NEW_LINE DEDENT arr = [ 2 , 3 , 4 , 10 , 40 ] NEW_LINE n = len ( arr ) NEW_LINE x = 10 NEW_LINE result = exponentialSearch ( arr , n , x ) NEW_LINE if result == - 1 : NEW_LINE INDENT print " Element ▁ not ▁ found ▁ in ▁ thye ▁ array " NEW_LINE DEDENT else : NEW_LINE INDENT print " Element ▁ is ▁ present ▁ at ▁ index ▁ % d " % ( result ) NEW_LINE DEDENT