In my previous article, I had covered the bubble sort. Today I am going back to the search area.
One would not think that you would learn a bit on karate in IT. Although we do have kata’s in software engineering (the continuous practice to make us masters), as well as one of the most common materials for a kata, which is the karate chop (aka binary search).
In binary search you basically keep on chopping up your intended search area in half, up until you find what you are looking for.
Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky
Donald E. Knuth
Binary search was first mentioned in a research paper around 1946. It was [Theory and Techniques for the design of Electronic Digital computers, edited by G.W. Patterson, 1 (1946), 9.7-9.8; 3 (1946),22.8-22.9] that introduced the idea of using a computer algorithm to perform this search. It also pointed at the one interesting property of the binary search. This being – it works best if the data is sorted first or in simple terms, you know which direction you should be searching in.
The idea of sorting to improve searching speed goes back to antiquity. The probably earliest known example was something called Inakibit-Anu tablet from Babylon dating back to c. 200 BCE. The tablet contained the famous babylonian 60-base numbers sorted, which made searching for a specific entry easier.
Before we’ll go into reviewing the code, please treat yourself to a quote that makes binary thinking probably easier.
Entrepreneurs love to view risk as binary. The more you put on the line, the greater the potential for reward.
Jason Fried
For the code example, I have again used Codingame. One of their ‘Batman’ tasks is well suited to wrap around the concept of binary searching. It also has some wicked animations, showing how the elements are being searched for. My code is located here. The very ugly main loop is shown below.
The implementation is simple though. We can assume this matrix is sorted, as we are always provided with the direction of where is what we are looking for.
Gustaw Fit 