Advanced Way to Search an Array in Python (for Self taught Devs)

Imagine your new manager clamoring about the slow speed of your company's application.

Based on your observation, a little optimization of the codebase which was "written in a hurry" would increase efficiency.

You decided to do exactly that.

A few hours later, you found a function that searches an array with hundreds of items from the database.

The problem with this function is that it runs linearly. And searching for a single item isn't different from looking for a needle in a haystack.

Cutting the time the function runs by half will make you the hero of the day.

But how would you do that?

Well, here comes...

Binary Search

What's Binary Search?

Binary Search is a search algorithm that belongs to a group of algorithmic design patterns called Divide and Conquer

Binary Search is an efficient algorithm for finding an item in a sorted list of items. The magic behind it lies in its ability to cut the list or array by half (logarithmic time) every time it does a search.

For example, an array with a length of:

10 will take approximately 3 steps to find 1 item.
100 will take approximately  7 steps to find 1 item.
1000 will take approximately  10 steps to find 1 item.
10,000 will take approximately  13 steps to find 1 item.
1,000,000 will take approximately  20 steps to find 1 item.

Wow!

That is really fast! And would truly help you save the day.

But how do you implement it?

Well, first, you have to understand how it is designed.

The concept is simple:

* Make sure your array is sorted.
* Find the start index of the array ~ (usually 0)
* Find the end index of the array ~ (usually length of array - 1)
* Find the middle of the array
* If your item is in the middle, return it.
* If your item is greater than the middle item, update the middle as the new start
* If your item is lower than the middle item, update the middle as the new end.

Let's see how it looks in code.

def binary_search(array, target):
     array = sorted(array) #sort the array
     start = 0
     end = len(array) - 1
     while start <= end:
        middle = start + (end - start) // 2 #find the middle
        item = array[middle]
        if target == item:
            return middle
        if target < item:
            end = middle - 1
        else:
            start = middle + 1
     return None

You did it!

At the end of the workday, you successfully optimized your code saving your organization extra run time. Your manager enters the standup call smiling ear to ear...and thanked you for it!

Your users are happier now. That function was really slowing things down for them.

You were named the hero of the week during the next day's standup!

And it ended happily ever after!