Binary Search in ES6

The binary search is an algorithm used to find the position of an element in a sorted array. This is one of my favorite algorithms because its not only performant, but also very easy to wrap your head around. In this post I’ll hope to explain some of what I’ve learned about the binary search, some practical use-cases (other than CS puzzles and interview questions), and examine an implementation of binary search in ES6 code. Lets get started shall we?

A binary search essentially divides a sorted array in half, recursively, narrowing down a list of possible elements that match the value provided. That’s it, honestly. It’s such a simple idea — just pick a point in the middle of an array, if the searched value is bigger than the point you picked, search the right half; otherwise, search the left. Repeat this procedure until you’ve found the value you’re looking for.

How about we visualize this with an example. You have an array with values [1, 3, 4, 5, 8, 10, 15, 18, 20, 21, 22], and you’re searching for 15. here’s how it works:

[1, 3, 4, 5, 8, 10*(start here), 15, 18, 20, 21, 22]

• 15 is > 5. so lets check the right half

[15, 18, 20*(middle of right side), 21, 22]

• 15 is < than 20. so lets go left

[15*(start here), 18]

• well what do you know, 15 is our match!!

Since the binary search recursivley cuts our possible matches in half, it is a logarithmic algorithm. Big O notation of O(log N+1) at worst case.

A great example of the binary search in practice is git-bisect. Git Bisect is a tool that performs a recursive binary search on a list of commits in order to find a bug-introducing commit. Git-Bisect is really great and I suggest you use it whenever you can!

Lets check out an example of binary search in ES6:

function binarySearch(array, val){
  'use strict';

  let minimumIndex = 0;
  let maxIndex = array.length - 1;
  let currentIndex;

  (function search(){
    currentIndex = Math.floor((minimumIndex + maxIndex) / 2);

    console.log(`curently looking between ${array[minimumIndex]} and ${array[maxIndex]}`);

    if (array[currentIndex] === val ){
      console.log(`FOUND IT! ${val} == ${array[currentIndex]}`);
      return;
    }

    if (val > array[currentIndex]){
      minimumIndex = currentIndex + 1;
    }

    if (val < array[currentIndex]){
      maxIndex = currentIndex -1;
    }

    search();
  })();
}

module.exports = {binarySearch};

Our ES6 code should be pretty straightforward here, but lets break it down:

• we create a few variables to set up our search. Our minimumIndex, and maximumIndex respectively. And a current index.
• we create a named IIFE to do all our recursion.
• we set our current index to whatever our bounds are (min and max index) divided by 2, rounded down.
• if the searched value is greater than current index, move our min index up currentIndex + 1
• if our searched value is smaller than current index, move our max index to currentIndex - 1.

And we repeat this until we find our match.

Lets see what this looks like in node:

js-cs-notes master % node
> let search = require('./binary-search');
> let arr = [1, 3, 4, 5, 8, 10, 15, 18, 20, 21, 22];
> let val = 15;
> search.binarySearch(arr, val);
curently looking between 1 and 22
curently looking between 15 and 22
curently looking between 15 and 18
FOUND IT! 15 == 15

And there you have it. A basic implementation of binary-search in ES6. I hope you found this at least half as fun as I did!