Binary Search Algorithm Made-Easy

Hello young minds! Today, we’re going to embark on a fascinating journey into the world of computer science and explore a magical tool called the “Binary Search Algorithm.” Don’t worry, we’ll break it down into bite-sized pieces so that even a 10-year-old can understand.

What is the Binary Search Algorithm?

Imagine you have a long row of boxes, each containing a special toy. Now, you want to find a particular toy, but you don’t want to check every single box because that would take a lot of time. What do you do? You use the magic of binary search!

Binary search is like a super-smart way of finding things quickly. Instead of going through each box one by one, you start in the middle. If the toy you’re looking for is in that middle box, great! If not, you cleverly eliminate half of the remaining boxes and continue the search in the remaining half. Repeat this process until you find the toy.

How Binary Search Algorithm works?

Suppose you have a data and it contains a row of numbers as shown below:

Now I have to find number “12”, in the above row.

A quick question:

How would you find it?

How would you tell the computer to find it?

If you know the answer good, if don’t. Do not worry this is what I am about to tell you.

How would you find it?

First we will look at the numbers and there it is the number “12”.

How would you tell the computer to find it?

Well, we can tell the computer to go through each number and if he finds number “12” then let us know. Bam done.

Now think about it, Is this method good? Yes but not very good.

What if we tell the computer to find number “500000” in a very big row of numbers then what? It will take computer a long time to find this number.

Speed is something that we need in computers. We want computer to find this number very fast. Imagine that you opened a Google website or a YouTube website to search for something, then a lot of results is shown to you. Now you go to one website, if it takes too long to open. What are you gonna do? Of course, You will move on to another website. This is why we want computers to find the number faster. How to achieve this? Well Read ON!

First we will tell the computer to start searching for this number from the middle as shown below:

Now, Is number “8” is number “12”. No, number “8” is less than number “12”, Now what do we do?

So Now we know that we will not find the number “12” if we go backwards (or go left side) from number “8” because all the other numbers (1,3,4,7) are still less than number “12”. We will tell the computer to remove all the numbers on left side. Now we have the below numbers left as shown below:

Now again we will search for number “12” from middle, It will look like this:

Now, Is number “14” is number “12” that we need. No, number “14” is greater than number “12”, Now what do we do?

Again, we know that we will not find the number “12” if we go forward (or go right side) from number “14” because all the other numbers (25, 30) are still greater than number “12”. We will tell the computer to remove all the numbers on right side. Now we have the below numbers left as shown below:

Now again we will search for number “12” from middle, but now there is no middle. What do we do?

We have two numbers left so what we will do is check if first number “11” is number “12”. What do you think?

Again we will apply the same method and remove the number “11”.

Now we will check if below is the number “12”.

Bravo, Congrats. We have find the number “12”.

This how the binary search algorithm works in real life. Now we will program this method in python language.

How to Do Binary Search in Python?

Here is a simple example in Python:

def binary_search(toy_list, target_toy):
    low = 0
    high = len(toy_list) - 1

    while low <= high:
        mid = (low + high) // 2
        guess = toy_list[mid]

        if guess == target_toy:
            return mid  # Found it!
        elif guess < target_toy:
            low = mid + 1  # Eliminate the left half
        else:
            high = mid - 1  # Eliminate the right half

    return -1  # If the toy is not in the list

if __name__ == '__main__':
   data_list = [1,3,4,7,8,11,12,14,25,30]
  
   print('Binary Search:', binary_search(data_list, 12))

This code line does this as shown below:

Python assign indexes to lists to identify which value is where. So, variable Low has value “1” and high has value “10” as shown in code line below:

low = 0
high = len(toy_list) - 1

Now we find the middle index point by adding the high and low value and divide by two (then rounding off to the nearest number), we get value “5”. This is what the below code do:

while low <= high:
        mid = (low + high) // 2
        guess = toy_list[mid]

Now we check based on three conditions,

• If the middle value is equal to “12”.
• If the middle value is less than “12”.
• If the middle value is greater than“12”.

This logic is implement in code below:

if guess == target_toy:
            return mid  # Found it!
        elif guess < target_toy:
            low = mid + 1  # Eliminate the left half
        else:
            high = mid - 1  # Eliminate the right half

So it will not find the number “12” then it will change the index value of high and low hence leaving the left side as shown in image below:

Now we will search our number “12” from middle value. As number “14” is greater than number “12”, we will remove the right side hence updating the index value as shown below:

Again we will apply the same method and remove number “11”. Then we have the number “12” that we need.

Congrats you did it.

This how we program this simple logic.

So what are the advantages or benefits of using this method? Well…

Advantages of Binary Search Algorithm:

1. Speedy Magic: Binary search is super fast because it eliminates half of the options at each step, making it much quicker than searching one by one.
2. Efficient: It works wonders on long lists, making it a powerful tool when you have a lot of toys (or data) to search through.

Then what are the disadvantages? Wait a sec, Here it is.

Disadvantages of Binary Search Algorithm:

1. Sorted Toys Only: Binary search requires the toys (or data) to be sorted. If your toys are all jumbled up, this magic won’t work.
2. Limited to Lists: Binary search is like a master of lists but might not be as helpful with other data structures like dictionaries.

Hmmm Ok. I understand. But how can we use this algorithm in real life?

Well we have a few examples.

Real-Life Examples and Scenarios:

Binary search isn’t just for finding toys; it’s used in real life too! Think about finding a word in a giant dictionary book. You open the book somewhere in the middle, check if your word is on that page, and then decide whether to look in the first half or the second half. That’s binary search in action!

Imagine you have a gigantic dictionary with thousands of pages, and you’re looking for the word “elephant.” Instead of flipping through each page one by one, you can use a strategy similar to binary search.

1. Open in the Middle: You open the dictionary somewhere in the middle. This is like randomly selecting a page and checking the word.
2. Compare the Words: You find a word on the page (let’s say it’s “giraffe”), and you compare it with “elephant.”
3. Choose a Half: Since “elephant” comes after “giraffe” in alphabetical order, you decide to focus on the pages that come after the current page.
4. Repeat the Process: Now, you repeat the process. You open the dictionary to the middle of the remaining pages and compare the word. You continue this process, narrowing down the possibilities with each comparison.
5. Found It: Eventually, you’ll reach a page where the word “elephant” is, and you’ve found what you were looking for!

Binary search in a dictionary works because the words are usually sorted in alphabetical order. This way, you can quickly eliminate half of the remaining pages with each comparison, making the search much faster than going page by page.

This strategy is similar to the binary search algorithm used in computer, where you efficiently narrow down the search result by comparing the target item with the middle item in a sorted list or array.

Here are a few more examples:

• Library of Books: Imagine a library with books sorted by title. Binary search helps you quickly find the book you’re looking for.
• Guess the Number: You can play a game where someone thinks of a number, and you try to guess it. Binary search helps you narrow down the possibilities with each guess.
• Phone Contacts: When you’re looking for a friend’s name in your phone contacts, you might use a form of binary search by jumping to a letter in the middle of the alphabet.

So, young explorers, the next time you play hide-and-seek with your toys or need to find something quickly, remember the magical binary search algorithm. It’s like having a wizard’s wand for searching in the world of computers! Keep exploring and have fun with the magic of coding!

Follow me for more: https://medium.com/@maxerom