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**

1 2 3 4 5 6 7 |
function binarySearch(SampleArr, item) { // code goes here }; let SampleArr = [1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35]; let item = 17; let itemIndex = binarySearch(SampleArr, item); |

**Define the middle position and item**

1 2 3 4 |
function binarySearch(SampleArr, item){ const midPoint = Math.floor(SampleArr.length / 2); const middleElem = SampleArr[midPoint]; }; |

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

1 2 3 4 5 6 7 |
function binarySearch(SampleArr, item){ ... // if middle item is right, lucky us no further search required if (middleElem== item) { return item; } }; |

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

1 2 3 4 5 6 7 |
function binarySearch(SampleArr, item) { ... else if (item < SampleArr[midPoint]) { // search item from left subset return binarySearch(SampleArr.slice(0, midPoint), item); } }; |

**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**

1 2 3 4 5 6 7 |
function binarySearch(SampleArr, item){ ... else if (item < SampleArr[midPoint]) { // search item from right subset return binarySearch(SampleArr.slice(midPoint+1), item); } }; |

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

1 2 3 4 5 6 7 |
function binarySearch(SampleArr, item){ ... else { // when we can't binarySearch an item return null; } }; |

**Finally…**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
function binarySearch(SampleArr, item) { const midPoint = Math.floor(SampleArr.length / 2); const middleElem = SampleArr[midPoint]; // if the middle item is right, lucky us no further search required if (middleElem == item) { return item; } else if (item SampleArr[midPoint]) { return binarySearch(SampleArr.slice(midPoint+1), item); } else { return null; } }; let SampleArr = [1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35]; let item = 17; let itemIndex = binarySearch(SampleArr, item); |

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

Ta