Hello people…! In this post we will discuss one of the most commonly used search algorithm, the Binary Search. In a search algorithm, we are given an element and a collection or a set of elements. If the given element exists in the given set, we must return where it is located, or otherwise, if it does not exist, our algorithm must be able to say it does not exist.
Binary Search Conditions
The given set must obey the following rules if we want to apply binary search –
- All pairs of elements in the given set must be comparable. Mathematically, this is called a totally ordered set.
- The given set must be sorted, in ascending or descending order.
Algorithm
Let’s say we are looking for 7 in an array A = {1, 2, 3, 4, 5, 6, 7, 8, 9}. Binary search compares the middle element (here 5) and the element to be searched (here 7). So, 5 is less than 7. Binary search says, “Okay so 5 is less than 7, so don’t bother about the elements left of 5 because they are less than 5 anyway. It will never be equal to 7. Continue the same job with the right half instead!”. So, now we will look at the elements right of 5 only.
Now, let’s sat the middle element is 8. This time Binary Search says, “Elements right of 8 are more than 8, they will never be equal to 7, so neglect the elements right of 8, carry on with the elements left of 8.”
So if you analyse this carefully, we are cutting the size of elements we are supposed to look at by half for each step.
To implement this algorithm, we use 3 variables –
- low – the lowest index of the searching range.
- high – the highest index of the searching range.
- mid – which is calculated by the formula below
Let us take the previous example array A = {1, 2, 3, 4, 5, 6, 7, 8, 9}. This time let us search for 9, and this time we will find the middle element using the formula above.
Initially, low = 0 and high = 8, which gives mid = 4. The middle element is not 9, but 5 which is less than 9, so we might find 9 only to the right of 5. So, we will assign low = mid + 1.
Now, low = 5 and high = 8, which gives mid = 6. Value 7 is less than 9, so we search in the right half of 7. We do this by low = mid + 1. (If we wanted to search in the left half, say for 6 example, we would do high = mid – 1).
Even now, the middle element is less than the required element, so we must search in the right half. So we do low = mid + 1.
Now our middle element is equal to what we want, so we return this index! So basically Binary Search goes up to when there’s only one element left. If that remaining element is not the element we want, then we can claim that the given set does not contain it.
Just imagine if we were searching for 10 in the above case, we would go up to the last element and find that even the last element is not equal to 10, so we return a -1 or some value which denotes that the element is not found.
The reason the formula for calculating the middle element isn’t a simple average is to avoid an integer overflow error. If we try to calculate,
when low and high are close to maximum values of an integer, they can cause an integer overflow. This is why we use the formula mentioned above.
Complexity
We make one comparison per iteration. So what is the worst case? Worst case occurs when the element is not present in the given set. Then we need to iterate until we have one element left. At each iteration, we reduce the range by half, so how many iterations should we perform to reach a single element?
It is log2 N! So the worst case complexity of binary search is O(log2 N). The best case would be if the middle element of the set is itself is the value we want to find, then, the complexity would be O(1).
Code
It is a fairly simple algorithm to code. Please try to write the code by yourself. If you get stuck, you can use my code below as a reference.
You can code the binary search using recursion too. But I prefer the iterative version as it does not have the recursion overhead and it will not produce a stack overflow error for large arrays.
Keep practicing! Happy Coding! 🙂