Introduction to binary search for beginners

Binary Search (HK)
🔗
Step by Step Binary Search Algorithm
🔗
(Fun) Binary Search Dance
🔗
Algorithm (MIT OCW)
🔗
Click here to suggest a better video or view suggestions..

Have you ever wondered how computers quickly find information in a massive list of data? One of the most efficient ways they do this is by using an algorithm called binary search. Whether you’re new to programming or just curious about how search algorithms work, this article will introduce you to binary search in a simple and explain the intuition behind it in a beginner-friendly way.

Binary search is a searching algorithm used to find the position of a specific value (often called the “target”) in a sorted list of items. It works by repeatedly dividing the list in half and narrowing down the search range until the target is found (or determined to be absent).

Think of it like searching for a word in a dictionary. Instead of flipping through every page (which would take forever), you open the dictionary in the middle, check if the word is on the left or right based on the ordering, and repeat the process until you find it. That’s essentially how binary search works!

Note: A sorted list is a collection of items arranged in a specific order, either ascending (from smallest to largest) or descending (from largest to smallest). For example, a list of numbers like [3, 7, 12, 18, 25] is sorted in ascending order, while ["zebra", "monkey", "dog", "cat"] is sorted in descending alphabetical order. Sorting makes it easier to search for specific items, as patterns and relationships between elements become clear. Many algorithms, like binary search, rely on sorted lists to work efficiently. Sorting can be applied to numbers, words, or any data that can be compared and ordered.

A Real-World Example: Finding Contact in the Phone Book

Let’s understand binary search with a simple, real-world example. Imagine you’re looking for someone named “Smith” in a phone book. Let’s assume that the phone books contains the list names in alphabetical order, similar to how a sorted list is arranged for binary search.

Here’s how you’d use a binary search-like approach:

  1. You open the phone book roughly in the middle. Let’s say you land on “Johnson”.
  2. Since “Smith” comes after “Johnson” alphabetically, you know to look in the second half of the book.
  3. You open to the middle of the second half. This time you land on “Robinson”.
  4. “Smith” comes after “Robinson”, so you again look in the latter half of your current section.
  5. You open to the middle again and find “Thomas”.
  6. “Smith” comes before “Thomas”, so now you look in the first half of this section.
  7. You repeat this process, each time cutting your search area in half.
  8. Within just a few flips, you find “Smith”!

This is exactly how binary search works! Instead of checking every page from the beginning (like “Adams”, “Baker”, “Clark”, etc.), you make intelligent guesses that eliminate half of the remaining pages each time. This method is much faster than flipping through every single page, especially in a thick phone book!

The Number Guessing Game

Let’s explore another fun example that demonstrates how binary search works. Imagine playing a number guessing game where your friend picks a secret number between 1 and 100, and you need to guess it. Here’s how you can use the binary search approach to find the number efficiently:

  1. Start by guessing 50 (the middle number between 1 and 100).
  2. Your friend tells you if the secret number is higher, lower, or correct.
  3. If it’s higher, you know the number is between 51 and 100.
    • Your next guess would be 75 (the middle number between 51 and 100).
  4. If it’s lower, you know the number is between 1 and 49.
    • Your next guess would be 25 (the middle number between 1 and 49).
  5. You continue this process, always guessing the middle number of the remaining range.
  6. Each guess eliminates half of the remaining possibilities.

The magic of this method is that you can find any number between 1 and 100 in just 7 guesses or fewer! This is the power of binary search - it quickly narrows down the possibilities by half with each step.

Here’s the summary of all the guesses:

  • Guess 1: 50 (Friend says “The secret number is greater than 50”)
  • Guess 2: 75 (Friend says “The secret number is lesser than 75”)
  • Guess 3: 62 (Friend says “The secret number is greater than 62”)
  • Guess 4: 68 (Friend says “The secret number is lesser than 68”)
  • Guess 5: 65 (Friend says “That’s the secret number I thought!")

As you can see, we found the number 65 in just 5 guesses, much faster than randomly guessing or checking every number from 1 to 65!

Before we dive into implementing binary search, it’s crucial to understand that this algorithm has specific requirements to function correctly. Let’s explore these prerequisites in more detail:

  1. Sorted Data:

    • The collection of items must be arranged in a specific order (ascending or descending).
    • Examples:
      • A phone book with names in alphabetical order
      • A list of numbers ordered in ascending order (from lowest to highest)
      • An array of dates sorted chronologically
    • Why it matters: The sorted nature allows us to make informed decisions about which half of the data to discard in each step. For instance, if you try to perform a binary search on an unsorted list, you might discard the half containing your target element, leading to a failed search.

  2. Random Access:

    • You need the ability to directly access any element in the collection by its position or index.
    • Examples:
      • Flipping to any page in a book instantly
      • Accessing any element in an array using its index
    • Why it matters: This allows the algorithm to “jump” to the middle of the remaining data in each step, rather than having to scan through all elements sequentially.

Why is Binary Search Important?

Binary search is incredibly efficient and widely used in computer science. Here’s why it’s so important:

  1. Lightning-Fast Search: Binary search is remarkably quick. It can find an item in a sorted list of 1 million elements in just 20 steps or fewer! This speed makes it invaluable for handling large datasets.

  2. Optimal Time Complexity: The time complexity of binary search is O(log n), which is significantly faster than linear search O(n). This means that as the size of the data increases, binary search becomes exponentially more efficient compared to simpler search methods.

  3. Versatile Applications: Binary search is used in a wide range of real-world applications, including:

    • Database systems for quick data retrieval
    • Search engines to find relevant results rapidly
    • Game development for efficient resource management
    • File systems to locate files and directories quickly

  4. Foundation for Problem-Solving: Understanding binary search helps develop critical thinking and problem-solving skills. It introduces key concepts like:

    • Divide and conquer strategies
    • Logarithmic time complexity
    • Efficient algorithm design

  5. Memory Efficiency: Binary search doesn’t require additional memory proportional to the input size, making it memory-efficient for large datasets.

By grasping the concept of binary search, you’re not just learning an algorithm – you’re gaining insight into fundamental principles of efficient computing and algorithmic thinking.

What’s Next?

Now that you understand the basics of binary search, you’re ready to dive deeper! In the next article, we’ll explore how binary search works in detail, with step-by-step explanations and visuals to make it even clearer.