Binary search and finding roots.

Binary search is one of my favourite algorithms. If you don’t know what it is, it is a searching algorithm with a logarithmic run-time and very simple logic, but it works only for sorted lists. Simply start in the middle element. If what you’re searching for is smaller then the middle element, go to the middle of the left side. If what you are searching for is bigger than the middle element, go to the middle of the right. Repeat this process until you find what you are looking for.

Surprisingly, this system can be used to find the square root of a number as we are searching for root in a sorted list of numbers on the number line. Suppose you want to find the square root of 9.

  • The middle of 0 and 9 is 4.5.
  • 4.5 squared is 20.25, not 9.
  • 9 is smaller than 20.25, so the square root of  9 should be smaller than 4.5.
  • 2.25, maybe? It is in the middle of 0 and 4.5.
  • However, 2.25 squared is 5.0625.

If you repeat that process over and over again(which I refuse to do), you will eventually reach 3, which is the correct answer.

In fact, you can even do this for cube roots, fourth roots, fifth roots, et cetera. Instead of checking the square of your current number each step, check the cube of the number power of 4, power of 5, power of… you get it.

I even created a program to execute this function, with the same logic I just explained. Down here is the gist for the program:

To use this program, click here.