Binary Search

• Searches for an element in a sorted array
• TC: log(n)
• SC:
  • 1 - iterative approach
  • log(n) - recursive approach - call stack

def binarySearch(arr, target):
    start, end = 0, len(arr)-1
 
    while start != end:
        mid = int(start + end-start/2)
        if arr[mid] == target:
            return mid
        elif arr[mid] > target:
            end = mid-1
        else:
            start = mid+1
 
 
if __name__ == '__main__':
 
    arr = [1,2,3,4,6,7,8,9]
    target = 6
 
    pos = binarySearch(arr, target)
    print(f'Location of element {target} is {pos}')