search.c

#include <assert.h>
#define CMP(a, b) (a > b ? 1 : (a == b ? 0 : -1))
int bsearch(const int arr[], int n, int k)
{
	int l = 0, m, cmp;
	assert(n > 0);
	while (l < n) {
		m = (l + n) / 2;
		cmp = CMP(k, arr[m]);
		if (cmp == 0)
			return m;
		if (cmp < 0)
			n = m;
		else
			l = m + 1;
	}

	return -(l + 1);
}

// 二分查找算法的优化
int binary_search(const int arr[], int n, int k)
{
	int left = -1;
	int step = n > 0 ? 31 - __builtin_clz(n) : 0;
        int slen = 1U << step;

	assert(n > 0);
	// 如果小于0的话，在数组的右半部分, 在范围(left, n), 长度为slen的部分查找
	// 否则的话在左半部分, 在范围为(left, slen), 长度为slen的部分查找
	// 经过这一步之后查找的长度就是slen了, slen=2^step, 只要经过step次查找就
	// 能找到要查找元素的位置了
        if (slen < n && CMP(arr[slen - 1], k) < 0)
		left = n - slen;
        switch (step) {
        case 31: if (CMP(arr[left + 0x40000000], k) < 0) left += 0x40000000;
        case 30: if (CMP(arr[left + 0x20000000], k) < 0) left += 0x20000000;
        case 29: if (CMP(arr[left + 0x10000000], k) < 0) left += 0x10000000;
        case 28: if (CMP(arr[left + 0x08000000], k) < 0) left += 0x08000000;
        case 27: if (CMP(arr[left + 0x04000000], k) < 0) left += 0x04000000;
        case 26: if (CMP(arr[left + 0x02000000], k) < 0) left += 0x02000000;
        case 25: if (CMP(arr[left + 0x01000000], k) < 0) left += 0x01000000;
        case 24: if (CMP(arr[left + 0x00800000], k) < 0) left += 0x00800000;
        case 23: if (CMP(arr[left + 0x00400000], k) < 0) left += 0x00400000;
        case 22: if (CMP(arr[left + 0x00200000], k) < 0) left += 0x00200000;
        case 21: if (CMP(arr[left + 0x00100000], k) < 0) left += 0x00100000;
        case 20: if (CMP(arr[left + 0x00080000], k) < 0) left += 0x00080000;
        case 19: if (CMP(arr[left + 0x00040000], k) < 0) left += 0x00040000;
        case 18: if (CMP(arr[left + 0x00020000], k) < 0) left += 0x00020000;
        case 17: if (CMP(arr[left + 0x00010000], k) < 0) left += 0x00010000;
        case 16: if (CMP(arr[left + 0x00008000], k) < 0) left += 0x00008000;
        case 15: if (CMP(arr[left + 0x00004000], k) < 0) left += 0x00004000;
        case 14: if (CMP(arr[left + 0x00002000], k) < 0) left += 0x00002000;
        case 13: if (CMP(arr[left + 0x00001000], k) < 0) left += 0x00001000;
        case 12: if (CMP(arr[left + 0x00000800], k) < 0) left += 0x00000800;
        case 11: if (CMP(arr[left + 0x00000400], k) < 0) left += 0x00000400;
        case 10: if (CMP(arr[left + 0x00000200], k) < 0) left += 0x00000200;
        case  9: if (CMP(arr[left + 0x00000100], k) < 0) left += 0x00000100;
        case  8: if (CMP(arr[left + 0x00000080], k) < 0) left += 0x00000080;
        case  7: if (CMP(arr[left + 0x00000040], k) < 0) left += 0x00000040;
        case  6: if (CMP(arr[left + 0x00000020], k) < 0) left += 0x00000020;
        case  5: if (CMP(arr[left + 0x00000010], k) < 0) left += 0x00000010;
        case  4: if (CMP(arr[left + 0x00000008], k) < 0) left += 0x00000008;
        case  3: if (CMP(arr[left + 0x00000004], k) < 0) left += 0x00000004;
        case  2: if (CMP(arr[left + 0x00000002], k) < 0) left += 0x00000002;
        case  1: if (CMP(arr[left + 0x00000001], k) < 0) left += 0x00000001;
        }

	left++;
	if (left < n) {
		int c = CMP(arr[left], k);
		if (c == 0)
			return left;
		if (c < 0)
			left++;
	}

	return -(left + 1);
}

// http://www.cs.technion.ac.il/~itai/publications/Algorithms/p550-perl.pdf
// http://en.wikipedia.org/wiki/Interpolation_search
int interpolation_search(const int arr[], int n, int k)
{
	int l = 0, r = n - 1, m;
	double inter = 0;

	assert(n > 0);
	while (l <= r) {
		if (arr[l] > k)
			return -(l + 1);
		if (arr[r] < k)
			return -(r + 2); // 下一个位置是r + 1

		inter = ((double)k - arr[l]) / ((double)arr[r] - arr[l]);
		m = l + (r - l) * inter;
		if (arr[m] == k)
			return m;
		if (arr[m] < k)
			l = m + 1;
		else
			l = m - 1;
	}

	return -(l + 1);
}