News for hackers. Stuff that matters.
Re:Nearly all binary search and merge sort implementations a... by gsg on Tuesday January 31, 2012 @06:47AM (#3532847)
You mean this one?

    int binary_search_pow2(const int a[], int len, int key) {
        int i = 0, step;
        for (step = len / 2; step > 0; step >>= 1)
            if (a[i | step] <= key)
                i |= step;
        return i;
    }
I thought that only worked for power-of-two sized arrays.
Re:Nearly all binary search and merge sort implementations a... by sesqu on Tuesday January 31, 2012 @09:38AM (#3533391)
I implemented one for practise, without assuming powers of two:

    int binarySearch(const int needle, const int haystack[], const int size) {
    	if (size==0)
    		return -1;
    
    	short log2 = 0;	// rounded down
    	for (int sz=size; sz>>=1; log2++);
    
    	int index = 0;
    	for (int flag=1<<log2; flag>0; flag>>=1) {
    		index |= flag;	// set
    		if (index>=size || needle<haystack[index])
    			index ^= flag;	// unset
    	}
    	return needle==haystack[index] ? index : -index-1;
    }