Searching: Binary Search!

Binary Search Algorithm: a Fun and Easy Guide with JavaScript Code

Oct 24, 2024

A young adventurer, with a curious expression and messy brown hair, pores over a worn, yellowed treasure map, illuminated by a warm, golden light, his bright blue eyes scanning the creased parchment for the next clue, as he sits cross-legged on the weathered wooden planks of an old, mystic dock, surrounded by rusty lanterns and frayed ropes, the atmosphere thick with anticipation, the words "Binary Search" emblazoned in bold, modern font, in silver ink, across the top of the map, like a cryptic message, as if the treasure itself is hidden in the code.

Hey there! Ready to level up your algorithm skills and unlock the magic of Binary Search? Great! Binary search is like using a treasure map 🗺 you don’t search aimlessly, you know exactly where to go 🧭️!

In this article, we're going to break down binary search into bite-sized, easy-to-understand pieces. We’ll also write some JavaScript code to see it in action. Whether you're a beginner or just need a refresher, you’re in the right place!

What is Binary Search?

Imagine you have a magical book 📚 with all the numbers from 1 to 100 listed inside, each on its own page. But here’s the trick: the numbers are sorted in increasing order. Now, say you're looking for the number 72.

Would you start from page 1 and flip through each page one by one? 😱 Of course not! That would take forever. Instead, you'd be smart and use binary search.

Binary search works by dividing the search space in half over and over again until you find your target. Sounds smart, right? Let's dive into it!

How Does Binary Search Work?

Start in the Middle:
Open the book right to the middle. Look at the number on that page. Is it the number you’re looking for? If yes, congrats! You’ve found it. If not, proceed to the next step.
Eliminate Half the Search Space:
If the number you opened to is greater than your target, you can safely ignore the right half of the book. If it’s less, ignore the left half. Now you’re only dealing with half as many pages.
Repeat:
Keep repeating this process: go to the middle of the remaining half, and eliminate half of what's left until you find the target.

Visualizing Binary Search

Let's make this fun and interactive! Imagine you’re playing a guessing game. You’re thinking of a number between 1 and 100. I’ll guess your number using binary search!

Rules:

You say if my guess is too high, too low, or correct.
I’ll adjust my guesses based on what you tell me.

Let’s start!

I guess the number is 50.
- Too high? Too low? Or correct?

Now you give feedback:

If too low, I’ll guess higher.
If too high, I’ll guess lower.

This guessing process is exactly how binary search works, each guess splits the range in half.

Concrete Example ✍️

We have an array of 10 items: arr = [10, 2, 5, 6, 8, 7, 1, 0, 15, 3]

PS: In order to use Binary Search, you need to have a sorted array, if the array isn’t sorted, binary search isn’t the way to go! (or maybe you can sort it 😉, but it depends on the situation).

Step 1:

A sorted array → [0, 1, 2, 3, 5, 6, 7, 8, 10, 15]
A number to search for: 8

Step 2:

Split the array into half: half1 = [0, 1, 2, 3, 5], half2 = [6, 7, 8, 10, 15]
Compare “8” with 5 (last element of half1) or with 6 (first element of half2)
8 is > 5, so, we drop the first half ~~half1 = [0, 1, 2, 3, 5]~~
We repeat the same for [6, 7, 8, 10, 15]
- half1 = [6, 7, 8], half2 = [10, 15]
- 8 is equal to the last element of half1!! We fouuund it ✨✨

We found our number in 3 iterations !!! That’s O (log n) !

Binary Search in JavaScript

Ready to see some code? Let's write a binary search function in JavaScript and find out how it works under the hood!

Here’s the code to search for a number in a sorted array:

function binarySearch(arr, target) {
  let left = 0; // starting index
  let right = arr.length - 1; // ending index

  while (left <= right) {
    let mid = Math.floor((left + right) / 2); // middle index

    if (arr[mid] === target) {
      return mid; // found the target, return its index
    }

    if (arr[mid] < target) {
      left = mid + 1; // target is on the right side
    } else {
      right = mid - 1; // target is on the left side
    }
  }

  return -1; // target not found
}

How It Works: A Step-by-Step Breakdown

Initial Setup:
We define left as the first index (0) and right as the last index (arr.length - 1).
Find the Middle:
We compute the middle index as Math.floor((left + right) / 2). This divides our array in half.
Compare the Middle:
- If the middle element (arr[mid]) is the target, return its index.
- If the middle element is less than the target, move the left boundary to mid + 1 (we discard the left half).
- If the middle element is greater than the target, move the right boundary to mid - 1 (we discard the right half).
Repeat until we either find the target or the boundaries cross (meaning the target isn’t in the array).

Let's Test It!

Suppose you have this array of sorted numbers:

let sortedArray = [1, 4, 7, 12, 24, 35, 47, 59, 68, 72, 85, 90];
let target = 72;

Calling our binary search function:

let result = binarySearch(sortedArray, target);
console.log(result); // Outputs: 9

The output is 9 because 72 is at index 9 in the array (remember, arrays in JavaScript are zero-indexed).

Why Binary Search is Awesome

Speed: Binary search is superfast compared to linear search. In a list of 1000 elements, binary search only requires 10 guesses to find the target (since it cuts the search space in half each time). A linear search would take up to 1000 guesses!
Efficiency: Binary search works in O(log n) time complexity. This means the larger the array, the more time we save. A linear search takes O(n) time, which gets slow as the array grows.

Ready to Play Binary Search Yourself?

Now it's your turn to take control. Here’s a simple exercise for you:

Modify the Code:
Add code to handle when the array is empty (hint: check if the array length is 0 at the start).
Add More Fun:
What if the array contains duplicate elements? How would you modify the code to return all indices of the target, not just the first one?
Game On!:
Create an interactive guessing game in JavaScript where you challenge the user to guess a number between 1 and 100. Use binary search to make the guesses!

Final Thoughts

You’ve done it! You've now mastered the magic of binary search. No more flipping through pages aimlessly. Whether you're hunting for buried treasure (a number in an array) or cracking the code in a game, binary search will be your go-to tool.

Summary:

Binary search is an efficient algorithm that divides the search space in half to find a target in a sorted array.
It works by repeatedly comparing the middle element with the target and discarding half of the array each time.
You can implement binary search in O(log n) time complexity, making it much faster than linear search.

Now go forth and conquer your coding quests with binary search!

🔔 Don't forget to subscribe to my blog and YouTube channel to stay updated with all the latest content, follow me on LinkedIn too, if you like to do so!

Mnt Code Blog

Discussion about this post