Iterative Binary Search Function


Given an array of positive integers. Write an iterative version of binary search to find an element in the array

Iterative binary search


Binary search can be easily implemented using recursion due to the divide and conquer nature of the algorithm however we can also do it using iteration. Please refer to the code below for more information.

Iterative Binary Search Program in C

Here is the code in C++

#include <iostream>

using namespace std;

//Receives input array along with left and right indexes
//Returns the index of the search key if it is found
//otherwise it returns -1
int IterativeBinarySearch(int A[], int key, int l, int r) 
	//As long as left index is less than right index
	while (l <= r) 
		//Middle element
		int m = (l + r) / 2;
		//If the search key on the left half
		if (key < A[m])
			//Update right index
			r = m - 1;
		//If the search key on the right half
		else if (key > A[m])
			//Update the left index
			l = m + 1;
		//We found the key
			return m;

	//Key was not found
	return -1;

//Main function
void main()
	//Input array (already sorted)
	int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
	//Search for 8
	cout << IterativeBinarySearch(A, 8, 0, 9) << endl;

Please leave a comment if you have questions or corrections. Thanks

Search Terms...

Leave a Reply

%d bloggers like this: