In this article, you will learn what is Binary Search Algorithm and how it works. We will discuss both Iterative and Recursive approaches. In the next article, we will discuss the implementation of binary search and the time and space complexity analysis.
Introduction
The Binary Search follows the “Divide and conquer” algorithm for searching an element. It divides the array into smaller and smaller parts according to the search element until it is found.
The main constraint for performing a binary search on an array is that the array has to be sorted in ascending order (we can do this by performing any sorting technique we will be learning in the coming articles). If the element is not in the given array, then -1 is returned indicating that the element is not found.
Understanding Binary Search
Now, let’s look at how actually the binary search works and then write an algorithm for implementing it.
- As we came to know the first requirement to perform the binary search is a sorted array (in ascending order). So, we need a sorted array. Let us consider the following array to understand this better. Let the search element be 4.
- After sorting the array, we initialize two variables to point to the beginning and the ending of the array say low and high respectively.
- Then we find the middlemost element in the array by using the formula
mid = (low + high)/2
- Now 6 is the mid-value and low = 0 and high = 6
- Now we have to compare the search element with the mid element. If it is equal then our search is complete and we will return the position of that element.
- If the mid value is greater than the search element, we must compare the search element with the middle element of the elements on the left side. This is done by changing the upper bound to mid-1.
- If the mid value is less than the search element, we must compare the search element with the middle element of the elements on the right side. This is done by changing the lower bound to mid+1.
- In our example case we are searching for the element 4 and the middle value is 6 which is greater than 4 so we move to the middle value of the left side elements by changing the upper bound to mid – 1 i.e., high = 2.
- Now we repeat the same process. The mid value now is 4 which is equal to the search value so the element is found.
NOTE: If the search key/element is 4 then we repeat the same process until the upper and lower bounds become equal. If the element is not found at that condition, then we return -1 indicating the search was unsuccessful.
Algorithm for Binary Search
The Binary Search Algorithm can be implemented in either of the two ways:
- Iterative Method
- Recursive Method
Iterative Method
The binary search algorithm can be implemented using loops which is an iterative method.
Let’s look at the algorithm and understand this,
do until the pointers low and high meet each other.
mid = (low + high)/2
if (x == arr[mid])
return mid
else if (x > arr[mid]) // x is on the right side
low = mid + 1
else // x is on the left side
high = mid - 1So, in the iterative approach, we use the mid-value and search for the element we repeat this process until the low and the high values are equal and then return false or ‘-1’ if the element is not found in the array.
The iterative implementation of binary is efficient in terms of space when compared to the recursive implementation as a copy of every variable is created in the recursive approach for every function call so the space complexity is high.
In terms of logic, both the Iterative and the Recursive approaches are the same.
Recursive Method
Now that we have seen how binary search can be implemented using the iterative (loops) method let’s understand the Recursive approach for Binary Search.
Let us first look at the algorithm for Recursive Binary Search,
binarySearch(arr, x, low, high)
if low > high
return False
else
mid = (low + high) / 2
if x == arr[mid]
return mid
else if x > arr[mid] // x is on the right side
return binarySearch(arr, x, mid + 1, high)
else // x is on the right side
return binarySearch(arr, x, low, mid - 1)The Recursive approach is also similar to the iterative method the only difference is we use the concept of recursion instead of loops.
That is all for the article, hope you got a good idea of what is binary search and the different algorithms to perform a binary search. Let’s look at the implementation of binary search and the complexity analysis in the next one.
Happy Learning!
