Time Complexity O(n log n)
# Python3 Program for recursive binary search.
# Returns index of x in arr if present, else -1
def binarySearch (arr, l, r, x):
# Check base case
#print(x, r)
if r >= l:
mid = l + (r - l) // 2
# If element is present at the middle itself
if arr[mid] == x:
return True
# If element is smaller than mid, then it
# can only be present in left subarray
elif arr[mid] > x:
return binarySearch(arr, l, mid-1, x)
# Else the element can only be present
# in right subarray
else:
return binarySearch(arr, mid + 1, r, x)
else:
# Element is not present in the array
return False
# Driver Code
arr = [ 2, 4, 8, -9, 14, 20, 69 ]
for x in (2**p for p in range(1, len(arr))):
#print(2*x+5)
result = binarySearch(arr, 0, len(arr)-1, (2*x+5))
if(result == True):
print (2*x+5, " - Element is present in the array")
break
if(result == False):
print ("Element is not present in array")
# Function call
