Binary Search — A Recursive way of searching

Today we are going to discuss what is binary search, how to implement it recursively, and benefits of using binary search to lookup element in a given set of data.

Binary search is a search algorithm where we divide the given set of elements from the middle and compare the element to be searched with the element in the middle. If the element is smaller than the middle, we repeat the process in the first half of the dataset otherwise in the second half until the element to be searched is equal to the middle element.

Algorithm

Let us go over the algorithm and understand how to implement the Binary search recursively.

In the above code snippet, considering the element to be searched in is denoted by variable key,
if low is greater than high, which means key not found and we terminate the algorithm.
In the next step, we calculate the mid index.
If the key is equal to the element at the middle index of the array, we return the mid.
If the key is greater than the element at the middle index of the array, we call our method binarySearch from index mid+1 to high.
If the key is smaller than the element at the middle index of the array, we call our method binarySearch from index low to mid-1.

Time & Space Complexity

Binary search follows a divide and conquer technique.

Time complexity: O(logn)
Whenever we come across an algorithm which follows a divide and rule technique i.e., divides the array in half with every iteration, the time complexity will be logarithmic.

Space Complexity: O(logn)
Binary search when implemented recursively use extra space because of the creation of call-stack.

Usage & Benefits

It narrows down the search dataset.
It is easier to implement.
It can be used to search an element/object in a huge set of dataset efficiently.
It can be used in other algorithms to simplify the end objective of the algorithm.

You have reached the end of the article, and ready to implement or use Binary search in real-life solutions.

See you guys in the next article, until then hasta luego.

Founder @Fundbakery. The fun on the journey is more interesting than the excitement of arrival.