Implementation

Binary search is one of the simpler concepts to understand, but tricker ones to implement. I highly recommend taking some time to internalize and understand the below template.

Example Problem

Template

def binary_search(list, target):
    left = 0
    right = len(list) - 1
    
    while left <= right:
    
        # Midpoint
        mid = (left + right) // 2
        
        # Target found
        if list[mid] == target: return mid
        
        # Midpoint value below target
        if list[mid] < target: left = mid + 1
        
        # Midpoint value above target
        else: right = mid - 1
        
        # 
        return -1