Iterative and Recursive Binary Search Algorithm

The major difference between the iterative and recursive version of Binary Search is that the recursive version has a space complexity of O(log N) while the iterative version has a space complexity of O(1). Hence, even though recursive version may be easy to implement, the iterative version is efficient.

Binary search is a search algorithm that finds the position of a key or target value within a array. Binary search compares the target value to the middle element of the array; if they are unequal, the half in which the target cannot lie is eliminated and the search continues on the remaining half until it is successful.

This search algorithm works on the principle of "Divide and Conquer".Like all divide and conquer Algorithms Binary Search first divide the large array into smaller sub-arrays and then solve Recursively(or iteratively). For this algorithm to work properly, the data collection must be in the "sorted" form.Binary search, by virtue of its progressively dividing method, has much lower time complexity of "O(log n)".

You can opt Binary Search using Iterative algorithm or Recursive algorithm, but both may successfully accomplish the same task.

What is Iteration Algorithm?

In the case of Iterative algorithms, a certain set of statements are repeated a certain number of time.An Iterative algorithm will use looping statements such as for loop, while loop or do-while loop to repeat the same steps number of time.

What is Recursive Algorithm?

Recursive algorithm, a function calls itself again and again till the base condition(stopping condition) is satisfied.

Let us track the search space by using two index start and end.Initialy low=0 and high=n-1(as initially whole array is search space).At each step,we find mid value in the search space and compare it with target value.There are three cases possible:

CASE1: If target is equal to middle, then return mid.

CASE2: If target is less than middle i.e target<A[mid], we discard all the elements in the right search space including mid element.Now our new high would be mid-1 while 'low' remains as it is.

CASE3: If the target element is greater than middle i.e target>A[mid],we discard all the elements in the left search space including mid element.Now our new low would be mid+1 while 'high' remains as it is.

Iterative Binary Search\

• The main() method of IterativeBinarySearch class starts off with defining a Array of size 6, named A.
• Key is the number to be searched in the list of elements.
• Inside the while loop, "mid" is obtained by calculating (low+high)/2.
• If number at position mid equal to key or target element then the control returns index of mid element by printing that the number has been found along with the index at which it was found.
• *Else, if key or target is less than number at position mid then the portion of the Array from the mid upwards is removed from contention by making "high" equal to mid-1.
• Else, it implies that key element is greater than number at position mid(as it is not less than and also not equal, hence, it has to be greater). Hence, the portion of the list from mid and downwards is removed from contention by making "low" equal to mid+1.
• The while loop continues to iterate in this way till either the element is returned (indicating key has been found in the Array) or low becomes greater than high,in which case -1 is returned indicating that key could not be found and the same is printed as output.

The pseudocode is as follows:

int binarySearch(int[] A, int x)
	{
        int low = 0, high = A.length - 1;
		while (low <= high)
		{
			int mid = (low + high) / 2;
			if (x == A[mid]) {
				return mid;
			}
			else if (x < A[mid]) {
				high = mid - 1;
			}
			else {
				low = mid + 1;
			}
		}
		return -1;
	}
Java
Copy

Output:

An element found at index 1

Recursive Binary Search

• Recursive implementation of binary search algorithm, in the method binarySearch(), follows almost the same logic as iterative version, except for a couple of differences.
• The first difference is that the while loop is replaced by a recursive call back to the same method with the new values of low and high passed to the next recursive invocation along with "Array" and "key" or target element.
• The second difference is that instead of returning false when the while loop exits in the iterative version, in case of the recursive version, the condition of low > high is checked at the beginning of the next level of recursion and acts as the boundary condition for stopping further recursive calls by returning false.
• Also, note that the recursive invocations of binarySearch() return back the search result up the recursive call stack so that true or false return value is passed back up the call stack without any further processing.

The pseudocode is as follows:

int binarySearch(int[] A, int low, int high, int x)
{
    if (low > high) {
        return -1;
    }
    int mid = (low + high) / 2;
    if (x == A[mid]) {
        return mid;
    }
    else if (x < A[mid]) {
        return binarySearch(A, low,  mid - 1, x);
    }
    else {
        return binarySearch(A, mid + 1,  high, x);
    }
}

Output

Element found at index 1

Conclusion

Both will have the same time complexity O(log(n)), but they will different in term of space usage.

Recursive May reach to "log(n)" space (because of the stack), in iterative BS it should be "O(1)" space complexity.

At the point of choice of recursive vs. iterative formulation is pretty much a matter of personal and local preference.

Some people find recursive code easier to understand. Some people are scared to death of recursion, or don't understand it, or have no clue about tail recursion optimization, and want explicitly iterative code everywhere.