News for hackers. Stuff that matters.
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;
    }

There are no comments on this comment yet.