Classic Binary Search - Code

Here is the implementation of binary search:

function binarySearch(arr, target):
    low = 0
    high = arr.length - 1

    while low <= high:
        mid = low + (high - low) / 2
        if arr[mid] == target:
            return mid
        else if arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1

Why low + (high - low) / 2? To avoid integer overflow. (low + high) / 2 can overflow if low and high are both large.

Why low <= high? The search space is valid as long as there's at least one element. When low > high, the space is empty.

Time: $O(\log n)$.

Space: $O(1)$ (excluding input array).