Wednesday, September 8, 2021

Dynamic Programming - Binary Search - Index function to find 2*x+5

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

No comments:

Post a Comment