How Binary Search Actually Works: A Deep Dive 🔍

Hey dev community! 👋🏻

In my last article, I talked about one of the most basic sorting algorithms: Bubble Sort. Bubble Sort is a fundamental algorithm used to sort data. It works by repeatedly stepping through a list, comparing adjacent elements and swapping them if needed. But what if we want to find a target within our sorted collection? There are several algorithms we can use, and today, we're going to look at one of the most efficient: Binary Search.

What is Binary Search?

Binary Search is a powerful algorithm designed to find the position of a target value within a sorted collection. It relies on the Divide and Conquer approach, cutting the remaining search space in half with each step. Trust me, that's much better than the slow linear search 😅

Mini analogy

Imagine you are looking up the word "Logarithm" in an alphabetical dictionary. You don't start at page 1 and flip through every page (that is linear search). Instead, you open the book right to the middle.

If the page starts with the letter M, you know "Logarithm" might be in the left half of the book because L comes before M. You then throw away the entire right half of the book.
If the page starts with the letter K, you know "Logarithm" might be in the right half of the book because L comes after K. You can drop the entire left half of the book here.

And you just repeat this process until you find your word. Perfecto 👌🏻

The little prerequisite

For binary search to work, the search space must be sorted or monotonic (consistently increasing or decreasing). If the data is sorted randomly, you can't discard half of the search range.

How it works

Binary search tracks the search space using two index pointers: low/left (the start of the range) and high/right (the end of the range). It then executes simple logical steps:

Initialize low = 0 and high = N - 1. N is the length of the items in your dataset.
Calculate the middle index (mid) of the current range.
Compare the element at mid with your target value:
- Matching case: If the element at the mid index matches your target, you've found it. Return mid.
- Target is smaller: If the element at the mid index is greater than your target, the target might be in the left half. Narrow your search space by updating the upper boundary: high = mid - 1.
- Target is larger: If the element at the mid index is smaller than your target, the target might be in the right half. Narrow your search space by updating the lower boundary: low = mid + 1.
Repeat steps 2 and 3 as long as low <= high. If low surpasses high, the target is not in the array, and you should return a value like -1 to signal that nothing was found.

Example implementation

Let's write a JavaScript implementation of this algorithm. I'll keep it simple with no noise or clutter.

function binarySearch(arr, target) {
  if (!Array.isArray(arr)) {
    throw new TypeError("Input must be a valid array.");
  }

  let low = 0;
  let high = arr.length - 1; 

  while (low <= high) {
    // A safe way to find the middle index
    // without risking integer overflow in langs like Java or C++
    const mid = low + Math.floor((high - low) / 2);
    const current = arr[mid];

    if (current === target) return mid; 
    else if (current > target) high = mid - 1; 
    else low = mid + 1;
  }

  return -1; 
}

In our code above, we used an inclusive upper bound, meaning the index high is included in our search loops. Some developers prefer to use an exclusive upper bound where high = arr.length. If you choose the exclusive approach, you just need to tweak your loop condition to while (low < high) and update your right-side boundary shift to high = mid. Both approaches work well, but the exclusive upper bound is better for things like finding where to insert a missing item.

Example use

Now, let's test our function. We will try to find the target number 7 in this sorted array: [1, 3, 5, 7, 9].

Iteration 1:
- Current boundaries: low = 0, high = 4
- Calculating the middle index: mid = 0 + Math.floor((4 - 0) / 2) = 2
- Element at mid (index 2) is 5.
- Compare 5 and target 7. 5 < 7, so our target might be in the right half.
- Update lower boundary: low = mid + 1 = 3.
Iteration 2:
- Current boundaries: low = 3, high = 4
- Calculating the middle index: mid = 3 + Math.floor((4 - 3) / 2) = 3
- Element at mid (index 3) is 7.
- Compare 7 and target 7. They match!

We just did it! 🎉 Our function will successfully stop right here and return the index 3.

And that's Binary Search for you! It's a simple logic change that makes a massive difference in performance once your arrays start getting big.

See you in the next article, where we will be looking into Merge Sort! ✨

DEV Community