Home > Algorithms, Job > Binary Search

Binary Search

January 19th, 2010 NamPham Leave a comment Go to comments

As a programmer, most of us have at least coded the binary search algorithm: the algorithm to find a value in a sorted array. The algorithm itself is clear and easy to understand:

?View Code CPP
1
2
3
4
5
6
7
8
9
10
11

int BinSearch::bSearch(int* arr,int n, int value){
	int left = 0;
	int right = n;
	while (left <= right){
		int mid = (int)(left+right)/2;
		if (arr[mid] == value) return mid;
		else if (arr[mid] < value) left = mid + 1;
		else right = mid - 1;
	}
	return -1;
}

However, the binary search algorithm’s capability is far beyond that. Given an array of number (real/int), we can find the element in that array which is closest to the given value. The idea is that we find a range [left,right] in array that is small enough and “close enough” to value .i.e a[left] < value < a[right], value < a[left] < a[right] or a[left] < a[right] < value:

?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12

int BinSearch::bNearSearch(int* arr, int n, int value){
	int left = 0;
	int right = n;
	while (right - left &gt; 1){
		int mid = (int)(left+right)/2;
		if (arr[mid] == value) return mid;
		else if (arr[mid] < value) left = mid;
		else right = mid;
	}
	if (abs(value - arr[right]) < abs(value - arr[left])) return right;
	else return left;
}

That’s it !

Categories: Algorithms, Job Tags:
  1. No comments yet.
  1. No trackbacks yet.