How to write a recursive binary search algorithm in JavaScript

A step-by-step example to getting O(log n) speed with a recursive solution

In a follow — up to a previous post of a step-by-step guide on how to write a binary search algorithm through iteration, this time we’ll tackle the same problem recursively.

Recursion was quite confusing the first time I encountered it. Like Christopher Nolan’s Inception, keeping track of function calls, inside of function calls, inside of function calls, inside of function calls…and their respective resolutions can be mind bending. So we’ll go through it step-by-step. I’ll use the same problem as in my previous article so we can compare easily.

Imagine we had this sorted array of integers, and we needed to write a function that tells us if a given integer, let’s say lucky number 7, is in there or not:

arr = [1, 2, 4, 5, 7, 8, 9]

We can plainly see that it is. And a simple for loop would eventually reach 7 and return true. But what if we wanted to do it faster because the array was gynormous?

Let’s declare a function recursiveBinarySearch that takes in our array, and the number we’re searching. Let’s also declare one variable to help us in our task:

function recursiveBinarySearch(n, arr) {
  let mid = Math.floor(arr.length / 2);
}

Mid represents the mid point of the array. Our array’s length divided by 2 is 3.5. Math.floor helps round down. So right away, Mid has the value of 3.

Next we’ll write a base case. In recursion, the base case is like your safety break. It’s the statement that will stop the recursion. Without one, it’s possible your recursion will continuously loop forever and be trapped…calculating…thinking forever…like our little stick figure friend.

function recursiveBinarySearch(n, arr) {
  let mid = Math.floor(arr.length / 2);
// base case
  if (arr.length === 1 && arr[0] != n) {
    return false;
  }
}

Our base case says that if the array only has one element, and that element isn’t the number we’re looking for, then we know we don’t need to look for anything, and we can immediately return false.

But we can add another option. What if we got lucky, and the number right in the middle is the number we’re looking for? Then we should return true and stop working further. So let’s add that too:

function recursiveBinarySearch(n, arr) {
  let mid = Math.floor(arr.length / 2);
// base cases
  if (arr.length === 1 && arr[0] != n) {
    return false;
  }
  if (n === arr[mid]) {
    return true;
}

Now comes the interesting part: recursive algorithm

One way that helps me understand recursion is to think about it as a chopping block. It can’t handle the entire input. But it can handle a smaller chunk of the input. Our goal is to figure out a way to call our function again, but with an ever decreasing smaller input.

Let’s make two conditions: one if the number we’re looking for (lucky number 7) is greater than the current value of the array’s element at the mid (3) position and one if it’s less:

function recursiveBinarySearch(n, arr) {
  let mid = Math.floor(arr.length / 2);
if (arr.length === 1 && arr[0] != n) {
    return false;
  }
if (n === arr[mid]) {
    return true;
  } else if (n < arr[mid]) {
    // we'll do something here later
  } else if (n > arr[mid]) {
    // we'll do something here later
  }
}

Let’s pause and think a bit deeper here…

Our array is sorted, and looks like this: [1, 2, 4, 5, 7, 8, 9]…

Our midpoint here is 3. The element at midpoint position is 5…

and the number we’re looking for is 7.

Thus, if we are to chop our input into a smaller chunk, we should get rid of the part where we know for a fact our number cannot be:

• Is n < arr[mid]? 7 is greater than 5, so this condition won’t satisfy, and we shouldn’t worry about anything before this point in the array…
• Is n > arr[mid]? 7 is greater than 5, so we know if our number is in the array it’s going to be after this position. So let’s call the function again with a smaller input- the same array after the midpoint. Here’s how we’d do that:

return recursiveBinarySearch(n, arr.slice(mid));

What this will do is return the function with a call of n (our lucky #7), and the array, but chopped up, or sliced, from the mid point on. So now our array looks like this: [5, 7, 8, 9].

Now we start all over again, from the top!

• With our new input, mid is now arr.length / 2, or 4 / 2, or 2.
• Our array’s length is 4, so first conditional is be skipped
• arr[2] = 8, which is not 7, so the next conditional is skipped
• But now our n (7) is less than arr[mid] (8), so we need another function call. Like before, if we know our number is less than the element at the array’s midpoint, we should ignore everything after this position, and only keep things before the midpoint of 2. Here’s how we do that:

return recursiveBinarySearch(n, arr.slice(0, mid));

What this will do is return the function with a call of n (our lucky #7), and the array, but chopped up, or sliced, from the 0th element (5) to the midpoint(8) — but not including it. So now our array looks like this: [5, 7].

We start back up at the top again, and here’s the full code for reference:

function recursiveBinarySearch(n, arr) {
  let mid = Math.floor(arr.length / 2);
if (arr.length === 1 && arr[0] != n) {
    return false;
  }
  if (n === arr[mid]) {
    return true;
  } else if (n < arr[mid]) {
    return recursiveBinarySearch(n, arr.slice(0, mid));
  } else if (n > arr[mid]) {
    return recursiveBinarySearch(n, arr.slice(mid));
  }

• With our new input, mid is now arr.length / 2, or 2/ 2, or 1.
• Our array’s length is 2, so first conditional is be skipped
• arr[1] = 7, which is also the number we’re looking for! So now the second conditional evaluates to true, and true is returned!

You’d think we’d end there- and technically we have. But the algorithm isn’t done.

Because we were inside of 2 recursion calls, those functions technically haven’t resolved until they get receive that return value (true) from the deepest nested call. It’s like our little stick figure friend is coming out of the inner layers of those rectangles into the outer layers with a package: the true return value, and giving it to himself one level up. Then that stick figure does the same, until the most outer version of himself gets the package.

This is referred to as recursion unwinding, and without this happening, the function would be waiting for an answer to its call indefinitely…

So next, the recursion call we made with made with an input of 7, and the array of length 4 ([5, 7, 8, 9]), gets resolved with a true value…

Then the recursion call we made with made with an input of 7, and an array of length 7 (the original array of [1, 2, 4, 5, 7, 8, 9]) gets resolved with a true value…

And ultimately, the output of true is outputted.

Does that make sense?

I know…it’s wild. But once you get the hang of it, through deliberate practice, it’ll serve as a useful method to divide and conquer complex problems.

Also, and harking back and the entire point of binary search, this algorithm is more efficient, as it found our lucky #7 in 3 iterations compared to 4 that would’ve been with a for loop. With such a small array, this difference is trivial. But if our array was gigantor, continuously cutting the space we have to look through in half can make a significant difference.

Thanks for reading!

And remember: grit > talent.