In computer science, searching and sorting are some of the most fundamental and widely studies problems. In this issue we talk about one of the most fundamental search algorithm, Binary Search.
In previous issue as an example, we tried to find a word in a dictionary by looking at each word and checking if it matches our desired word (key), it is an example of linear search where we look at each element in solution space and match it with the key. In dictionary words are in an alphabetical order, so our solution space was sorted, which makes it easier for humans to look for a word in a dictionary and this is fundamentally inherent for binary search. We assume the search space is already sorted, and we climb the problem with divide and conquer type algorithm.
So given a search space, here a dictionary and our search word/key K, incorporating divide and conquer, we divide our dictionary in half, say L keeps the left half, R keeps the right half and M is the middle element, so now we look onto three scenarios all arising from M. If our key K matches M, voila! We are done. If it does not then we look for two other scenarios, if K>M, we discard L and make R our new search space and start over with same search method, just a change in search space, conquering the smaller problem. As you might have guessed if K<M, we discard R and find solution in L.
Here is a pseudo-code that might clarify things for you,
Input: sorted search space S and search key K
BINARY_SEARCH(S, K):
m = S.length/2
L = S[1 to m-1]
M = S[m]
R = S[m /2+1 to S.length]
If K == M: return m
else if K>M: return BINARY_SEARCH(R, K)
else: return BINARY_SEARCH(L, K)
We can improve the space efficiency of this psuedo-code by dividing the search space with array indexing, if our search space is stored in an array. It’s a good exercise to try it by yourself, as it is more space efficient in practice. For starters we can use binary search to find square root of a number.
Binary search due to its efficiency is highly regarded and is a go to algorithm for search problems. It is a huge improvement over linear search. It is widely used in many areas of computer science, predominantly in database search. Although as technology grew up the search algorithms became more complex but they still take the ideas from binary search. Even today you can use binary search to search for better hyperparameters for your Machine Learning algorithm or search through a huge ordered database. In following issues we will discuss sorting algorithms so you can sort databases by yourself and search for your key.
5 Feb 2024.
Next in series: Time Complexity and Bounds of Algorithms.