Binary Search

 

   

    For this weeks tasks I decided to write an algorithm on a technique called binary search. I was introduced to a really great algorithm book last week by Ashur that I have been reading and learned this new technique. It actually is really simple and makes me wonder why you didn't think of it before but it is really useful. I am going to try to break it down in really simple terms since most of my code has explanations on it. 

    Let's just say for example if I told you I am thinking of a number from 0-100. Every time you guess a number I will tell you that you are either too low or too high and to guess again. What do you think is the lowest amount of guesses it will take for you to guess the number I am thinking? What number would you start at? Since the numbers 0-100 are sorted and we know the position at every location we can use a technique called binary search. We know that 1 will always be before 10. We know that 63 will always come after 45. This means our data is sorted in a specific way.

    In the technique binary search since our data is sorted we can split it right down in half. The first guess would be 50. That is because if we guess 50 and we are wrong we will know if the correct number is less than or greater than 50! We eliminate half the numbers! If the number I was thinking of was 56 I would tell you the number is too low. That means now you just have to focus on the numbers 50< x <=100.  We then split those numbers down the middle again by guessing 75. I would tell you you're too high and again we split the data in half from 50< x <75. If you were to guess again if you follow the same technique you might guess 62. I would tell you again you're too high but now you're down to 50<x<62. If you break that down again using binary search you would guess 56 and guess the correct number! It took you 4 guesses to get to that number. Using this technique the most guesses you would have to use looking through data of 100 elements is only 7 guesses.

    The thing about Binary search is you dont start seeing the magic until you are dealing with a large sorted database. With 100 elements the max a binary search algorithm would take is 100 guesses (in programming its not really guesses but how many times the algorithm searches through the data). However if you crank that up to a database of lets just say 100,000 elements it would only take 16 guesses! That means the more sorted elements you have the more efficient a binary search technique will be.