Binary search is one of the most fundamental and efficient algorithms in computer science. It allows us to find a specific item in a sorted list by repeatedly dividing the search space in half. The key requirement is that the input list must be sorted. Let's see how it works with an example where we search for the number eleven in this sorted array.
The first step in binary search is to find the middle element of the array. We calculate the middle index using the formula: middle equals low plus high divided by two. For our array with indices from zero to nine, the middle index is zero plus nine divided by two, which equals four. So the middle element is nine at index four.
Now we compare our target eleven with the middle element nine. Since eleven is greater than nine, we know that our target must be in the right half of the array. We can safely eliminate the left half, including indices zero through four, and focus our search on the right half with indices five through nine. This single comparison has eliminated half of our search space.
We continue the binary search process. In the second iteration, we find the middle of indices five through nine, which is index seven with value fifteen. Since eleven is less than fifteen, we search the left half. In the third iteration, we find the middle of indices five and six, which is index five. The element at index five is eleven, which matches our target. We have successfully found the target in just three steps!
To summarize binary search: it is an efficient algorithm that works only on sorted arrays. Each comparison eliminates half of the remaining search space, giving it a time complexity of O log n. For an array of n elements, binary search needs at most log base two of n steps, making it much faster than linear search for large datasets. This logarithmic efficiency makes binary search one of the most important algorithms in computer science.