Binary Search

Computer Science

Someone once asked me, “What is computer science and why is it so fascinating to study?” To answer that question, Computer Science is the study of algorithmic processes and computational machines. Computer Science is such an interesting and exciting field thanks to the things you can create thanks to the knowledge in this field.

Binary search algorithm

One of the many algorithms that makes computer science so fascinating is the binary search, which is a truly effective and convenient search algorithm that finds a target value within a sorted list or array (that allows constant-time access to an i-th element). Though, binary search can be used to solve a wider range of problems. According to Wikipedia, it can also be called a half-interval search, logarithmic search, or binary chop. It works by repeatedly dividing in half the portion of the list that could contain the item until you have narrowed down the possible locations to just one.

How fast is Binary Search?

One of the most common ways to use binary search is to find an item in an array. Binary search is much faster than linear search, when the array has many elements. An important note is that the array must be sorted first to use binary search. Let’s take an example to see how much faster Binary Search is than linear search. The Tycho-2 star catalog contains information about the brightest 2,539,913 stars in our galaxy. Assume that you want to search the catalog for a particular star, based on the star’s name. Normally, one needs to go through every star to find the one that they’re looking for. If the one that they are looking for is located at the end of the catalog, they have to look 2,539,913 times. But if the catalog was sorted alphabetically by star names, binary search would not have to examine more than 22 times, even in the worst case!

Your Task

Here is the task: Given a sorted array arr[] of n elements, write a function to see if a given element x is in arr[]. If element x is in arr[], return True. Else, (if element x is not in arr[],) return False.

First, compare the target value to the middle element of the array. If they are not equal, the half in which the target cannot be in is eliminated (do you know how to identify which half to eliminate?), and the search proceeds on the remaining half, again taking the middle element to compare to the target value, and repeat this until the target value is found or the interval is empty.

Recommended: Please solve it on your own first, before moving on to the solution.

We ignore half of the elements just after one comparison. Here is how:

1. Compare z with the middle element.
2. If z matches with the middle element, we return True
3. Else If z is greater than the mid element, then z can only lie in the right half subarray after the mid element. So we recur for the right half.
4. Else (z is smaller) recur for the left half.

Solution

Here is the solution (Python 3):

def find(array, x):
    left = 0
    right = len(array)-1
    while left < right:
        mid = int((left + right)/2)
        if array[mid] == x:
            return True
        elif array[mid] > x:
            right = mid
        else:
            if left == mid:
                if array[right] == x:
                    return True
                else:
                    return False
            left = mid
    return False

Then, I will create an array/list of random integers from 0 to 100, called arr:

from random import randint
arr = sorted(randint(-100,100) for n in range(0,50))

Finally, I will use the function I just created, “find” to check if the number “-96” is in the array/list or not:

find(arr, -96)

Output:

False

You can use this code to find if any integer, any float, or even any string is in an array or not!

Implementation issues

“Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky.”
— Donald Knuth (a close friend with Ronald Graham, whose office at UCSD I used to visit)

Did you know? According to Wikipedia, when Jon Bentley assigned binary search as a problem in a course for professional programmers, he found that ninety percent failed to provide a right solution after several hours of working on it, mainly because the incorrect implementations failed to run or returned a wrong answer in rare edge cases(a problem or situation that occurs only at an extreme operating parameter). A study published in 1988 shows that accurate code for it is only found in five out of twenty textbooks.

Conclusion

In conclusion, Binary search is an algorithm that exploits the sorted property of an array to eliminate half of the search space iteratively and gains significant speed comparing to sequential search/linear search. Thanks to great computer scientists, like Donald Knuth, Gene Myers, Ronald Graham, John Hopcroft, and many others, there are many other specialized data structures designed for fast searching. Yet, Binary Search remains the simplest and effective algorithm that is still widely used.