Lifecode

Search a sorted array by repeatedly dividing the search interval in half. Begin with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise narrow it to the upper half. Repeatedly check until the value is found or the interval is empty.

There are several algorithms on searching a value within an array. As stated above, binary search is one of the fastest and most efficient searching algorithms. Though, one must provide a sorted array, and to sort an array, I suggest the Merge Sort Algorithm. Here’s my C++ function for the binary search algorithm.

template <typename T>
bool binSearch (T sKey, T *sArr, int arrSz) {
	int low, high, mid;
	low = 0; high = arrSz;
	do {
		mid = (low + high) / 2;
		if (*(sArr + mid) == sKey) {
			return true;
		} else if (*(sArr + mid) < sKey) {
			low = mid + 1;
		} else {
			high = mid - 1;
		}
	} while (mid != 1 && mid != arrSz);
	return false;
}

Basically it does, what the binary search algorithm does. It takes 3 arguments, the search key, the array to be searched, and the size of the array. Here’s an example application:

int main () {
	int arr[10] = {1,2,3,4,5,6,7,8,9,10};
	if (binSearch(2, arr, 10)) {
		cout << "Found!" << endl;
	} else {
		cout << "Not Found!" << endl;
	}
	return 0;
}

Have fun!