Binary Search — An Iterative way of searching

Today we are going to discuss what is binary search, how to implement it iteratively, 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.

int low = 0;
int high = arr.length - 1;

while (low <= high) {
int mid = low + (high - low) / 2;

if (key == arr[mid]) {
return mid;
} else if (key > arr[mid]) {
low = mid + 1;
} else {
high = mid - 1;
}
}

return -1;

In the above code snippet, we take two indexes, low set to the beginning of the array and high set to the last element in the array.
Running loop over the array till low is smaller or equal to the high index, we calculate the mid index in each iteration.
Considering the element to be searched in is denoted by variable key,
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 set the low index to mid+1 element.
If the key is smaller than the element at the middle index of the array, we set the high index to mid-1 element.
If the key is not found in the array, we return -1;

Time & Space Complexity

Binary search follows a divide and rule 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(1)
Binary search when implemented iteratively doesn’t use any extra space and hence consumes constant space throughout its execution.

Usage & Benefits

It narrows down the search dataset.
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.