Description

Binary search is a Search Algorithm for sorted lists which works by checking the value at the middle index, and then if its wrong guessing at a new middle index.

Runtime

O(log(n))

Visualization

Pseudocode

Pick the middle item.
If it’s the target, return its position.
If it’s too small, search only in the second half.
If it’s too big, search only in the first half.
Repeat until the target is found or nothing is left to check, then return nothing.

Code

def binary_search(arr, target):
    start = 0
    end = len(arr) - 1

    while start <= end: #This must be =
        mid = (end+start)//2 # note the +

        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            start = mid + 1 # we explude the middle
        elif arr[mid] > target:
            end = mid - 1 # we exclude the number we guess

    return None