Binary search

Binary search is a search algorithm to find a value in a sorted array. It works by starting at the middle of the array and checking if the target value is higher or lower than the middle value. If it is lower, the algorithm then treats the bottom half as the new array and repeats the process of checking the middle value until the target value is found. If the target is higher than the midpoint, the top half of the array is used.

Example in Python:

def binary_search(array, target):
    min = 0
    max = len(array)
    while min <= max:
        mid = (min + max) // 2
        if array[mid] < target:
            min = mid + 1
        elif array[mid] > target:
            max = mid - 1
        else:
            return mid
    # Not found
    return -1

Purpose

The advantage of using binary search over a simpler "check every element" approach is speed. Since each step of the algorithm approximately halves the number of elements that need to be searched, each doubling of the size of the array only adds one iteration to the "while" loop above, as opposed to doubling the number of steps. In other words, the number of steps required grows in proportion with the base-2 logarithm of the size of the array. In algorithmic complexity notation, binary search has O(log n) time complexity.