ansi_c_pg054_ch03_ex01.c

/*
 * Exercise 3-1.
 * Our binary search makes two tests inside the loop, when one would suffice
 * (at the price of more tests outside.) Write a version with only one test
 * inside the loop and measure the difference in run-time.
 */


#include <stdio.h>
#include <stdlib.h>



int
bin_search(int x, int v[], int n)
{
	int             low, high, mid;
	low = 0;
	high = n - 1;

	while (low < high ) {

		mid = (low + high) / 2;
		if (x <= v[mid])
			high = mid;
		else
			low = mid + 1;

	}

	mid = (low + high) / 2;
	if (v[mid] == x)
		return mid;

	return -1;
}


int
binsearch(int x, int v[], int n)
{
	int             low, high, mid;
	low = 0;
	high = n - 1;
	while (low <= high) {
		mid = (low + high) / 2;
		if (x < v[mid])
			high = mid + 1;
		else if (x > v[mid])
			low = mid + 1;
		else
			return mid;
	}

	return -1;
}

int main() {
	int v[1000] = {0};

	printf(" index = %d\n", bin_search(10,v,sizeof(v)/sizeof(int)) );
	printf(" index = %d\n", binsearch(10,v,sizeof(v)/sizeof(int)) );
}