First of all, I'd like to mention that I’m not a great fan of very complex algorithms that I can use only on a theoretical basis. At the other extreme, I also don't like algorithms that are so trivial that it takes only a short time to figure them out.
My idea of a perfect task or algorithm is one whose adaptation can improve a slow solution, but whose use is not obvious. Moreover, such an algorithm may be useful in everyday life, not just in the world of computer science or in solving theoretical problems. One such algorithm is the binary search.
Why? Well, the binary search algorithm is very intuitive. Many people use binary searches from childhood without being aware of it. For example, when you search for words in a dictionary, you don't review all the words; you just check one word in the middle and thus narrow down the set of remaining words to check.
The binary search is not restricted to searching for an element in a sorted sequence; if it were, the algorithm would be considered trivial and uninteresting. An interesting application of the algorithm is binary search on the result. For example, imagine that we want to find the minimum size needed for a square office that must freely accommodate all the employees of a company. We can perform a binary search for that size rather than sequentially checking all the possible sizes. We usually estimate the minimum and maximum sizes over which we do a binary search. Next, we just check some middle value and the interval can be halved again, and so on. That's a lot of saved time.
There are plenty of algorithmic tasks that require a binary search to achieve a model solution. They appear during recruitment interviews, in exams and in programming competitions. Indeed, they appear in a few Codility Tasks. So, a couple questions for you to ponder:
I’ve made the binary search the centrepiece of our programming lesson No 14. Check it out for more examples, explanations and exercises, and let me know if it was useful to you!
And of course, keep your eyes posted for our next Challenge coming out December 2016!
© 2009–2016 Codility Ltd., registered in England and Wales (No. 7048726). VAT ID GB981191408. Registered office: 107 Cheapside, London EC2V 6DN