BINARY SEARCH ALGORITHM with Python
Imagine you have a really long list of numbers, arrange in order of ascending or descending, and you’re just looking for one number out of the really long list. It’s obviously going to be a rather stressful task looking through the long list until you find your number, not just that but you’re probably going to waste a lot of time while you’re at it to. So that leaves most wondering, is there possibly any way I could perform this task without wasting so much time or going through so much haste.
So, what do we do? Well, we look at it from a programmer’s point of view, write a simple code that can fish out the number you’re looking for out of the large list, and your good to go, right? Well, not exactly. Depending on how many variables this number we are looking for is mixed up in, the processing speed of the program will become slower and slower.
That’s where the efficiency of a Binary search Algorithm comes in.
What is a Binary Search Algorithm?
This is a function that makes finding a specific number, out of a large set of numbers, arranged in order, faster and easier. To put it in basic terms, it looks for a needle in a hay stack.
This program searches for a given number by having them arranged in order and splitting them into two halves and searching a half at a time.
For the fact that the numbers are arranged in an order (either ascending or descending), the code takes the length of the numbers in the list (the number of numbers in the sequence to be processed) starting from zero to whatever the total number of numbers is, and divides it by two looking for the middle number in the list of numbers.
Let’s take the table above for example. The number we are looking for is twenty-three (23).
As you can see in the table, the boxes are numbered from zero (0) to nine (9). In the boxes are random numbers arranged in ascending order.
Next, the code locates the middle number in the list of numbers. There are ten (10) boxes each with a number in them as seen in Fig 1. The code divides ten (10) by two (2) to find the middle number, which in the case of Fig 2 is sixteen (16).
Now the main search begins. The code takes the number we are looking for (let’s call it the missing number (23)) and puts it side-by-side the middle number (16), it then identifies the larger number. In this case the missing number is larger than the middle number. Since the numbers are arranged in an ascending order, the missing number will be located to the right of the middle number, everything to the left of the middle number, including the middle number will be discarded because the missing number is larger than they are.
The entire process will repeat its self on all the numbers to the right of the middle number (16), including locating the new middle number.
The process continues to repeat with the same principles until the missing number is located.
Writing a Binary Search Algorithm Code
To use the Binary Search Algorithm in python, we will have to define it first. Defining it is basically just like, writing the formula to a mathematics problem before you solve it, whereas, in this case, defining it is important because, before now, python doesn’t know the formula for a Binary Search Algorithm, so we define it at the beginning under a given name (Binary_Search), and give the program the parameters to know which line of code should be executed and when.
Fig 4 shows the first three lines of my code. Here, I basically just set down the parameters which the Algorithm is majorly focused on.
“Number”, which represents all the numbers in the list, and “Item”, which represents the specific number we are looking for.
Next, we want to identify the first and last numbers in the list, these are represented as ‘Left’ for the first number in the list and ‘right’ for the last number in the list. The second line is for the code to start the counting of the numbers from zero. To explain further, Let’s assume all the numbers in the list are arranged side by side in boxes, just as it is in the first three Figures, the first box is numbered as zero.
The Third line of the code is basically telling the system “After you count the total number of boxes (numbers), minus one from the result and use the answer as the number for the last box”. If you are wondering why it has to minus one, it’s because the first box is numbered ‘0’ and when the program counts the boxes, it starts from ‘1’.
The first two lines of code in Fig 5 tells the program how to locate the middle box. it takes the first box which is numbered ‘0’ and adds it to the number of the last box, then it’s divided by two, the result is located among the boxes which are already numbered from ‘0’ to whatever the total number of numbers is.
Line number nine (9) is where the main Binary Search code begins. when the program reaches this point, it takes the missing number and comperes it to the middle number, if its less than the middle number, the program discards everything to the right of the middle number including the middle number, this is because the numbers involved are arranged in ascending order.
If the missing number is greater than the middle number, the program discards everything to the left of the middle number including the middle number. If the middle number is the same as the middle number, well then, the missing number has been located.
Now, working on my own project, I decided to use a much larger range of numbers. As seen in Fig 6, I used a range of numbers from zero ‘0’ to One hundred million ‘100,000,000’, and set the program to look for the number ‘5,426,998’.
If you recall in Fig 4, I defined the binary search with “number” and “item” in a bracket beside it. In Fig 6, I've brought back that line with “ordered_list” in place of “number” and “search_item” in place of “item”. When the code is run, these representations will substitute the representations from the initial formula in Fig 4.
The rest of the code tells the program to print the number when it’s located. If the number is not located, the code will print “not found”, meaning the missing number is not among the range of numbers the program searched.
Binary Search Algorithm in Everyday Life
All this time, I’ve been talking about how Binary Search makes finding things easier and faster, one would wonder if it only applied to numbers, well, it goes beyond just numbers. In fact, a lot of us apply Binary Search to what we do every day and we don’t even realize it, I for one never realized it, not until I actually thought about.
A very basic example of Binary Search in everyday life is looking for something in the dictionary. Assuming you’re looking for the alphabet ‘K’, naturally, you’ll open the dictionary to any page at random, depending on what alphabet page you happen to open to, if the alphabet is after ‘K’, you’ll discard the alphabet as well as everything after it, and if it’s before ‘K’, you’ll discard the alphabet as well as everything before it. That’s basic Binary Search in play there.
It’s not just in the use of Dictionaries, when you’re searching for a specific chapter in the novel you’re reading and so on like that.
