What do Hitler, Napoleon, and Julius Caesar have in common?

They have all won major battles using the simple yet effective method of divide and conquer.

Divide and conquer has always been a fantastic approach for solving complex problems. This also stands true for data retrieval.
Binary search, based on the principle of divide and conquer, is a widely used search algorithm.

Try it yourself

Consider that you want to look for the word ‘Search’ in the dictionary.

Intuitively, you would open the dictionary in the middle and see if the first letter of the page comes after or before the letter ‘S’.

Let’s say that the letter you arrived at is ‘N’. Since ‘S’ comes after ‘N’ in the alphabet, you would then ignore the first half of the dictionary and divide the second half into two parts.

Now, say that you arrived at the letter ‘T’.

This process continues until you intuitively take to linear searching through pages of the letter ‘S’ to find the word.

Now consider a much bigger dataset. Let us say you want to find your name in a register that contains the names of all people in the world. If you go linearly, this might take you hours or even days to find your name. However, the same can be accomplished by binary search in no more than 33 iterations.

Prerequisites to Binary Search

Binary search has three simple prerequisites:

1. Your dataset must be sorted
2. Your dataset must be sorted
3. Your dataset MUST be sorted

Okay, now that you have a sorted dataset, let’s begin searching!

What is binary search?

Binary search, also known as half-interval search, logarithmic search, or binary chop in computer science, is a search technique that locates a target value inside a sorted array. It does so by dividing the sorted array and focussing on only the “relevant” or “valuable” half and ignoring the rest.

Search Algorithm

1. The required element should be compared to the centre element.
2. We return the mid index if the required element is equal to the middle element.
3. Else If it is bigger than the mid element, it can only be found after the mid element in the right half subarray. As a result, we repeat the process for the right half.
4. Otherwise, repeat for the left half.

Try it yourself

Try implementing binary search in your preferred language using this algorithm. You may take help from the code snippets below. Feel free to reach out to us in the comments section if you find any bugs!

Code: C (Recursive implementation)

Output: Element is present at index 4

Code: C++ (Iterative Implementation)

Output: Element is present at index 4

Code: Python3 (Recursive implementation)

Output: Element is present at index 4

Code: Java (Iterative implementation)

Output: Element found at index 4

Time complexity analysis

While implementing binary search, the target element may be at three kinds of positions:

1. Middle of the array (Best case)
2. First or last element of the array (Worst case)
3. Anywhere except the cases above (Average case)

The Best case time complexity of the binary search algorithm is O(1).

The Average and Worst case time complexity is O(log2n).

This time complexity is significantly better than the linear search algorithm, whose average and worst-case time complexity is O(n).

Add finishing touches to your knowledge!

Since Binary search is a quick way for searching through sorted databases, it is often used in debugging. Suppose you have 100 versions of a code, each of which is different from the other. The 1st version displays the correct output, but the 100th version doesn’t.

An efficient way to find the broken version would be to run a binary search through all the versions. The versions are logged in a Version Control System in sorted order, so don’t worry about that. Check out the code in the 50th release, build it, and see if the bug is still there.

Continue dividing until you discover when the bug was introduced. This approach comes in quite handy especially if you make small commits.

Test your understanding

Q1. Given an input array = {5,9,11,15,21} and target element = 21. How many iterations are done until the element is found?

1. 5
2. 2
3. 3
4. 4

Q2. Given an array = {23, 41, 52, 68, 84, 91,102} and target element = 102. What are the mid values (corresponding array elements) generated in the first and second iterations?

1. 68 and 91
2. 68 and 102
3. 52 and 84
4. 52 and 91

Improvements on Binary Search algorithm:

Congrats! You have learned how to implement the binary search algorithm. But there is always room for improvement, right?

One possible way is to reduce the worst-case time complexity to O(1); you may check if the target element is equal to the first or last element of the array right in the beginning.

You discovered the wonders of Divide and Conquer and explored binary search in detail! So, the next time you are faced with looking through a large dataset, like a dictionary or your closet, look through its sections instead :)

Before you leave...

Binary search forms the basis of a Binary Search Tree.

If you want to learn about it in a similar article, drop a comment below and let us know your interest.

And if you enjoyed learning the fundamentals of binary search through this article, share the knowledge with your fellow programmers and your social circle. Maybe someone out there really needs this resource, and you might be helping them out by sharing it.

Happy Coding!