Iterative Binary Search Function

Problem

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

Iterative binary search

Solution

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++

//Includes
#include <iostream>

//STD
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
		else
		{
			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...

Comments are closed.

%d bloggers like this: