#bsearch

We sifted through numerous arrays to search for and return a specific element in labs. A typical process we use is a linear search. We iterate through an array, compare each current element to the rest for each round until we find a match of what we are looking for. Most commonly used linear search methods are select, find, each and other more variations of iterations for searching.

But what happens when the array size we’re working with isn’t just 10 elements, but a million? A linear search sounds expensive.

This is where a binary search comes in handy. To do a binary search, elements must be sorted!

If this was a linear search, we would compare each element to our target (in this case, the number 77). That would be a total of 37 comparisons.

In binary search, it goes straight to the middle of the array (the middle position can be computed with array.length / 2) and asks if that index or position holds the value we are looking for.

If it is, it breaks out of the loop and returns the value. If not, two possible things are asked:

Is array[position] > target? No. Proceed to the next question.

Is array[position] < target? Yes! So get rid of array[position] and all the elements before that.

Our new middle element would now be 79.

So again we ask:

Is array[position] < target? No.

Is array[position] > target? Yes! Thus, we get rid of array[position] and all the elements after that .

Our new middle element would now be 68.

The array[position] < target (68 is less than 77), thus we get rid of array[position] and all the elements before that.

Our new middle element is now 74.

Since 74 is less than 77, we get rid of that element and everything before that.

We are finally left with the last two elements to compare with each other.

We finally found the match!

Bottomline: how long did it take?

Here’s a tally of our total comparisons for each type of search:

A linear search would take us 48 comparisons.

A binary search would take us 6 comparisons.

(If we had a million pugs in our array, instead of taking a million comparisons to find the pug we want, the binary search method brings it down to just 21 comparisons. A million vs 21?! Cool, huh!)

Here’s a code sample using the binary search concept:

But that code looks ugly. Let’s refactor and use the binary search (.bsearch)method instead!

Why not use a hash instead to go straight to the value you need?

It all boils down to memory.

Imagine designing a cell phone. If you use a hash table for a cell phone address book, additional memory is needed to sort the values since you need to display the values in alphabetical order. So, by using a hash table you have to set aside memory to sort elements that would have otherwise be used as storage space.