Exercise_1.py

# Python code to implement iterative Binary  
# Search. 
  
# It returns location of x in given array arr  
# if present, else returns -1 

#TC of binary search is O(log n) since we halve the work to be done at each division
#SC is also o(log n) as we only use the part that potentially has the element
def binarySearch(arr, l, r, x): 
  
  #write your code here
  n = len(arr)
  l = 0
  r = n - 1

  while l <= r:
     m = (l + r) // 2
     if arr[m] == x:
        return m
     elif arr[m] <x:
        l = m + 1
     else:
        r = m - 1
  return -1

  
# Test array 
arr = [ 2, 3, 4, 10, 40 ] 
x = 1
  
# Function call 
result = binarySearch(arr, 0, len(arr)-1, x) 
  
if result != -1: 
    print("Element is present at index % d" % result )
else: 
    print("Element is not present in array")