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.