Building Coding Intuitions: Binary Search (Iterative Approach)

Establishing dexterity around Algorithms (Part 1)

Introduction

When it comes to coding, algorithms and incorporating them intuitively in your code has always been daunting, specially for beginners.

Algorithms, the how, why and when transcends whatever programming language you’re learning and can be the difference between a good programmer and a great one.

In this series of articles, we will try to explore and build intuition around different algorithms and familiarize ourselves enough to not be scared and optimize our code using them.

Divide and Conquer?

The very basic idea while learning the binary search is the divide and conquer strategy.

Imagine you have a thick victorian household inventory which is ofcourse written alphabetically. Your task is to find a specific word, let’s say a ‘Gold Spoon’. Intuitively the first thing that you’ll do is open it at a random page. Suppose that page has items starting from ‘M’. Your work is now halved as ‘G’ comes before M so there’s no need of looking the later part of the book. Doing this again and again will give you the Gold Spoon and is the basic idea around the binary search algorithm.

Dividing the main problem into multiple smaller sub problems and solving them in order to get the result is the foundation of this strategy.

How it Works?

It’s imperative or a pre-requisite that the array you’re taking should be sorted, (like how the inventory was sorted alphabetically). Binary search only works when the elements are sorted in order.

Let’s take an example of this list. We have a list of 15 elements and as you can see, sorted in ascending order.

Suppose the number that we are searching for is 42.

If you don’t think about any approach and start with a simple linear search (searching in a sequential manner)from the 1st element, your code will require 11 iterations to find the result which can be computationally exhausting in the long run and ofcourse has a time complexity of O(n), which here would be 15!

To solve issues like this, where your data and time complexity is large, we lean towards ways to optimize the code. This is where Binary Search proves to be an efficient technique.

Lets take a look at the problem again. For this approach we will be using 2 pointers low(l), the lowest(starting) location and similarly high(h), the ending location.

From the book analogy we have to open a random page, which in this case we do by finding out the Middle Value (mid) which is l+h/2.

In this example if we calculate the middle value we’ll get, do we have the number we’re looking at 8?

As the number on the 8th position is 29, even though it’s not the number we needed, we now know that we can ignore the entire portion between l and mid as 42 is higher than 29, saving us 8 iterations.

Now that we have our portion worked out for us, we will iterate the steps. In this new portion, intuitively we will start from the 9th position as its the starting of the portion we’re considering and the end pointer remains the same, mathematically, it will be:

l = mid+1

Iterating the steps again will take us to new values and we’ll do the same thing, until we find the number that we need.

In this situation, intuitively, we can see that 47 is greater than 42 hence the new high will be

h= mid-1

After iterating it again,

We’re finally at a position where the low, high and middle are the same value, indicating, we found the number!

Now a very curious scenario always comes in mind that what if the number we’re finding is not in the list?

Lets take the same list again and suppose the number is 30 which is clearly not in the list

Through the iterative calculations, we’ll get something like this:

We were able to iterate our results 4 times but in the 5th iteration, the high value became lower than the low value, which is not the behaviour of the pointers, indicating that the algorithm has failed to find the answer or simply the number is not present in the list.

From this example, its clear that h>l in all conditions for the answer to be conquered!

Let’s take a look at the iterations of the above example, starting from calculating the mid values, in a tree format for a clear understanding:

The maximum time taken depends on the height of the tree [log (n)]. In this case, the maximum number of iteration (n) is 4. Take any number from the list and try it yourself.

Earlier we also touched upon the time complexity of the linear search, if we calculate the the time complexity of binary search it’s O(log n), where n is the number of iterations, which is 4 in this case, significantly lower than O(15)

Pseudo Code

As the algorithm transcends programming languages, let’s write a pseudo code for establishing a clear understanding.

Here, array represents the sorted array you're searching through(we took a list in our example), and target is the element you're trying to find.

The algorithm starts by setting low to the beginning of the array and high to the end of the array. It then enters a loop where it calculates the middle index mid of the current search range.

BinarySearch(array, target):
    low -> 0
    high -> length(array) - 1 #As the indexing starts from zero
    
    while low <= high:
        mid -> (low + high) / 2
        
        if array[mid] = target:
            return mid
        else if array[mid] < target:
            low -> mid + 1
        else:
            high -> mid - 1
            
    return not_found

If the value at the mid index is equal to the target, the algorithm returns the index where the target was found. If the value is less than the target, the search range is narrowed to the right half of the current range. If the value is greater than the target, the search range is narrowed to the left half of the current range.

The loop continues until the low index is greater than the high index, at which point the algorithm terminates and returns a value indicating that the target was not found.

Python Code

As python is a very beginner friendly language, I converted the above example into code:

def binary_search(array, target):
    low = 0
    high = len(array) - 1
    
    while low <= high:  # O(log n) iterations
        mid = (low + high) // 2  # O(1)
        
        if array[mid] == target:  # O(1)
            return mid
        elif array[mid] < target:  # O(1)
            low = mid + 1  # O(1)
        else:
            high = mid - 1  # O(1)
            
    return -1  # O(1)

# List of numbers
numbers = [3, 6, 8, 12, 14, 17, 25, 29, 31, 36, 42, 47, 53, 55, 62]

# Target value to search for
target = 31

# Call the binary_search function
result = binary_search(numbers, target)

if result != -1:
    print(f"Target {target} found at index {result}")
else:
    print(f"Target {target} not found")

Conclusion

Binary Search stands as a remarkably efficient and powerful technique for locating specific elements in sorted arrays. Its brilliance lies in its ability to consistently halve the search space, leading to a logarithmic time complexity of O(log n). So go on, get your hands dirty and look forward to more algorithms :)