Binary Search Algorithm

Description

The binary search algorithm is a divide and conquer algorithm, that takes a sorted array as an input. It works by comparing the searched value (key) to the middle element of the array. If they match, then its index is returned. If the key is less than the middle element, the algorithm is invoked on the left sub-array, otherwise it is invoked on right sub-array. This continues until the key is found or the input array is reduced to zero.

Recursion tree

Recursion tree

The running time of the algorithm can be calculated using the master method :
MathMagic130210_1
Where:
a – the number of recursive calls;
b – the input size shrinkage factor;
d – the exponent in the running time of the work, outside of the recursive call.

Recursive Implementation

Code:

template<class T>
int RecursiveBinarySearch(const T* sortedArray, const T& key, int start, int end)
{
	if (start > end)
		return -1;
	size_t middle = (start + end) / 2;
	if (key == sortedArray[middle])
		return middle;
	if (key < sortedArray[middle]) 
		return RecursiveBinarySearch<T>(sortedArray, key, start, middle - 1);
	else
		return RecursiveBinarySearch<T>(sortedArray, key, middle + 1, end);
}

Usage:

int sortedArray[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9};
// Positive test case
int index = RecursiveBinarySearch<int>(sortedArray, 3, 0, sizeof(sortedArray) / sizeof(sortedArray[0]));
cout << index << endl; 
// Negative test case
index = RecursiveBinarySearch<int>(sortedArray, 11, 0, sizeof(sortedArray) / sizeof(sortedArray[0]));
cout << index << endl;

Iterative Implementation

The iterative implementation narrows down the searched range for each cycle of a loop.
Code:

template<class T> 
int IterativeBinarySearch(const T* sortedArray, const size_t arraySize, const T& key)
{
	int start = 0;
	int end = arraySize;
	size_t middle;
	while (start < end) {
		middle = (start + end) / 2;
		if (key == sortedArray[middle])
			return middle;
		if (key < sortedArray[middle]) 
			end = middle - 1;
		else
			start = middle + 1;
	}
	return -1;
}

Usage:

int sortedArray[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9};
// Positive test case
int index = IterativeBinarySearch<int>(sortedArray, sizeof(sortedArray) / sizeof(sortedArray[0]), 3);
cout << index << endl; 
// Negative test case
index = IterativeBinarySearch<int>(sortedArray, sizeof(sortedArray) / sizeof(sortedArray[0]), 11);
cout << index << endl;
You can leave a response, or trackback from your own site.

Leave a Reply