# Python program to find an element x

# in a sorted array using Exponential Search

# A recursive binary search function returns

# location of x in given array arr[l..r] is

# present, otherwise -1

def binarySearch( arr, l, r, x):

if r >= l:

mid = l + ( r-l ) / 2

# If the element is present at

# the middle itself

if arr[mid] == x:

return mid

# If the element is smaller than mid,

# then it can only be present in the

# left subarray

if arr[mid] > x:

return binarySearch(arr, l,

mid - 1, x)

# Else he element can only be

# present in the right

return binarySearch(arr, mid + 1, r, x)

# We reach here if the element is not present

return -1

# Returns the position of first

# occurrence of x in array

def exponentialSearch(arr, n, x):

# IF x is present at first

# location itself

if arr[0] == x:

return 0

# Find range for binary search

# j by repeated doubling

i = 1

while i < n and arr[i] <= x:

i = i * 2

# Call binary search for the found range

return binarySearch( arr, i / 2,

min(i, n-1), x)

# Driver Code

arr = [2, 3, 4, 10, 40]

n = len(arr)

x = 10

result = exponentialSearch(arr, n, x)

if result == -1:

print "Element not found in thye array"

else:

print "Element is present at index %d" %(result)