Binary Search

Suppose we want to find an element in a list. The simplest approach would be linear search, where we iterate throughly the list and check each element until we either find a match or reach the end of the list.

If the element we are looking for happens to be the $k$th element in the list, then our best case scenario means we will need to execute $k$ operations. If the element isn't in the list, then for a list of $n$ elements, our worst case scenario means we will have executed $n$ operations, meaning $O(n)$, or linear time is required.

Binary search offers an improvement to a time complexity of $O(\log n)$, or logarithmic time.

The concept is as follows. Suppose we have an array containing $n$ elements. We sort the array and then initially check the element at the $n/2$ position. If the element is the one we're looking for, then we're done. Since we're working with a sorted array, we compare the element we just checked with our target element. If the target element is less than the element at the $n/2$ index, we can immediately filter out the second half of the array and thereby reduce our search space by $1/2$. We continually check the element at the mid-point of each reduced search space until we find our element or run out of elements to check.