Thread: Binary search - two functions

Hello,

I've written two functions doing binary search. This wasn't a homework assignment, I just did that for fun. Which of the two functions do you like more?

Code:

int binary_search1(int *arr, int count, int item)
{
	int l, r, mid;
	l = 0; r = count - 1;
	mid = (r + l) / 2;

	while (l <= r && arr[mid] != item) {
		if (arr[mid] > item)
			r = mid - 1;
		else 
			l = mid + 1;
                mid = (r + l) / 2;			
	}
	
    if (arr[mid] == item)
	return mid;
    else
        return -1;
}

int binary_search2(int *arr, int count, int item)
{
	int l, r, mid;
	l = 0; r = count - 1;
	
	while (l <= r) {
		mid = (r + l) / 2;
		if (arr[mid] > item)
			r = mid - 1;
		else if (arr[mid] < item)
			l = mid + 1;
                else
                        return mid;
	}
	
    return -1;
}

I suggest you read the article I wrote about binary search on my website. In contains code very similar to both of those versions and discusses why they are reasonably inefficient. It then goes on to show the most efficient version.

In this case your #1 is actually worst because it does 2 item comparisons each time through the loop. The bottom one does 1.5 item comparisons on average. A good version will do exactly 1 item comparison each time through.