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.