elias-search.c

gistfile1.c

#include <stdio.h>

static int N;

static int findN(void)
{
	int min, max, mid;

	// index starts from 1; search using Elias encoding (i.e. search at 1,2,4,8,16,... and then perform binary search)
	for (max = 1; ; max *= 2) {
		if (! (max < N))
			break;
	}
	// binary search within [min, max)
	min = max / 2 + 1;
	while (min != max) {
		mid = (min + max) / 2;
		if (mid < N)
			min = mid + 1;
		else
			max = mid;
	}
	return min;
}

int main(int argc, char **argv)
{
	for (N = 1; N < 1000; ++N)
		printf("find(%d) = %d\n", N, findN());
	return 0;
}