In this article, I will be taking you through one of the searching algorithms, Binary search, step by step and perform a complete analysis of it.

This technique only works for sorted arrays and is similar to a dictionary where we roughly start from the middle, and if we are looking for a word with E, for instance, then we tend to discard the second half of the dictionary and only look for the word in the first half of it and repeat the process till we find the desired element.

Algorithm

The binary search algorithm is mainly used when there is a large number of elements in an array and it requires frequent search of elements. In such a case, the array is maintained in a sorted form by doing a one-time operation and binary search is conducted frequently on it. The process of binary search is detailed below.

• We divide the array into two halves and find the middle element.
• We first check if the key element(element to be searched) is the middle element, if not, we check if the number greater than the middle element or less than middle element.
• If it’s greater than the middle element, we search in the second half discarding the first.
• If it’s less than the middle element, we search in the first half discarding the second.

The following gif will make you understand the algorithm better!

Time complexity

If there are n elements in the array, then in each level the array is halved and the search is reduced to one-half of the array.
Therefore, for n elements, there will be Log2n iteration.
Hence the order of binary search is O(Log2n)