Binary Search

Binary search using Iterative Method

# Time complexity O(log(n)) and space complexity is O(1)
### Using three pointers - left, right and middle
### We keep adjusting the three pointers and quit when 
### left pointer crosses the right pointer

def binarySearch(array, target):
    left = 0
    right = len(array) - 1    

    while left <= right:
        middle = (left+right) // 2
        potentialMatch = array[middle]

        if target == potentialMatch:
            return middle

        elif target < potentialMatch:
            right = middle - 1

        else:
            left = middle + 1

    return -1

array = [0,1,21,33,45,61,71,72,73]
target = 33

binarySearch(array=array,target=target)

3

Binary search using Recursion

# O(log(n)) time complexity ! O(log(n)) space complexity

def binarySearch(array,target):
    return binarySearchHelper(array,target,0,len(array)-1)

def binarySearchHelper(array,target,left,right):
    if left > right:
        return -1

    middle = (left+right) // 2
    potentialMatch = array[middle]
    if target == potentialMatch:
        return middle
    elif target < potentialMatch:
        return binarySearchHelper(array,target,left,middle-1)
    else:
        return binarySearchHelper(array,target,middle+1,right)  

binarySearch(array,target)

3