Classic Binary Search

Given a sorted array and a target, find the index of the target or return $-1$ if not found.

Example: Find $7$ in $[1, 3, 5, 7, 9, 11, 13]$.

$1.$ $low = 0$, $high = 6$, $mid = 3$. $arr[3] = 7$. Found!

Example: Find $6$ in the same array.

$1.$ $mid = 3$, $arr[3] = 7 > 6$. Search $[0, 2]$.

$2.$ $mid = 1$, $arr[1] = 3 < 6$. Search $[2, 2]$.

$3.$ $mid = 2$, $arr[2] = 5 < 6$. Search $[3, 2]$.

$4.$ $low > high$. Not found. Return $-1$.

Each comparison eliminates half the remaining elements.