Paul Allsopp en Maths, computer teaching, Engineers and Technicians, Software Developer Software Developer • Performance Food Group 17/5/2016 · 2 min de lectura · +500

Binary Search

I came across a question by a jQuery user who asked how to: “Insert a row into a table alphabetically on a row cell”

The two answers that were suggested to him used an iterator to go over every row of data in the HTML table, and check to see if his value should be slotted in at that point. I poked myself in the eye at this point wishing I had never read those answers, and concluding that I needed to point out why. So here goes…

In a binary search solution you first check to see if the datum you are searching with, is less than the first row of data, by the field you are matching on. If it is, then your row goes at the top of the dataset. If however it does not, you can check to see if your data is greater than the last row in the dataset. If it is, then your data goes at the end of the dataset.

On the third hand, if it is neither, then you can use a binary search to find the correct location for your row.

You start by splitting your total number of rows into two. You then check to see if the data on the last row of the first set is greater or less than the data you want to insert. Whatever the outcome, you have just reduced the dataset you are searching in by 50%, and you can throw away the subset of data which your data does not fall into.

So let’s say your data is less than the last row in the first set. You now divide that set into two and check if your data is lesser or greater than the last row of your new first set. Again, whatever the outcome you have just reduced the dataset by 50%. So in the grand scheme of things, in 2 iterations you have reduced the size of the original dataset to 25%.

In a table of 10,000 rows, you have performed 4 searches in total and reduced your set of data to 2,500 possibilities. Pretty amazing, huh?

You then continue with this method of splitting and checking until you find where your row needs to be. Let’s try an example!

Let’s say I have a set of 9 numbers, and I need to insert a number in that set such that the set remains consecutively numbered.

For this we will insert the number 7 into a set of (1, 2, 3, 4, 5, 6, 8, 9, 10).

Check 1: is 7 less than 1? No!
Check 2: is 7 greater than 10? No!

Split the dataset into two sets: (1, 2, 3, 4, 5) and (6, 8, 9, 10).

Check 3: is 7 greater than the last row of the first set(5)? Yes!

So now we can discard that first set as we know our number(7) is greater than all of the individual numbers in that set. We now have a single set of data(6, 8, 9, 10), which we will split into two sets: (6, 8) and (9, 10)

Check 4: is 7 greater than 8? No!

So now we can discard that second dataset, leaving us with just two numbers: 6 and 8.

We already know that our number cannot be less than 6 because we would not have discarded the first dataset earlier. We also know that our number cannot be greater than 8 because we just discarded the dataset it would be in if it were.

Therefore it must be in between.

Binary search: 4 checks.
Iterative search: 7 checks.

Now, imagine that cost saving on a much bigger scale.