Binary Search Made Easy

Have you ever picked up a dictionary to search for a particular word? Guess what, you are likely performing a Binary Search. How? I hear you ask through the Grapevine. Imagine you’ve been asked to search for the word terrarium in a dictionary.

One way to approach the task is to search the dictionary from front to back A through Z in a linear fashion but it’s a waste of good time. Certainly not a very developer-esque approach.
A natural approach is to split the dictionary two ways. For example, A-M, N-Z, using the first letter t in terrarium as a hint telling us which half of the book to start our search. In this case, t is in the section of N-Z, so that’s where we start. We simply repeat the process all over again until we find it. Voila!

Why Binary Search?

Binary Search is a quick algorithm particularly when compared with a linear search. Only half the data is searched at any step. For example, it is possible to search through 1024 values in 10 steps, every time.

Note that Binary Search is only useful out when you have a sorted list of items, i.e A-Z.

To implement Binary Search elegantly we need to write the function recursively. A Recursive function is simply a function that calls itself with different parameters.
A non-recursive solution also exists, see here.

To the Code 👉

To bring this idea to life, let’s try locating the number 17 in an array [1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35]

First lets define the Function scaffold so we know where things go

Define the middle position and item

Set Condition for when middle item is what item we’re searching for

When middle item < item, we carry on searching recursively in the left subset of data I.e array from position 0 to midPosition

When middle item > item, we carry on searching recursively in the right subset of data I.e array from position midPosition to the end of the array

Lastly we want to return null when we can’t locate the item in the array

Finally…

 

Hope this has helped you level up your knowledge on binary search. Go on, give it a go.

Ta

Related Posts