Array searches: Morin's code is probably representative of what most people use in industry... i.e., not that good :x

B-tree.cpp

// b-tree
// Before
template<unsigned B, typename T, typename I>
I btree_array<B, T,I>::search(const T &x) {
        I j = n;
        I i = 0;
        while (i < n) {
                I lo = i;
                I hi = std::min(i+B, n);
                while (lo < hi) {
                        I m = (lo + hi) / 2;
                        if (x < a[m]) {
                                hi = m;
                                j = hi;
                        } else if (x > a[m]) {
                                lo = m+1;
                        } else {
                                return m;
                        }
                }
                i = child((unsigned)(hi-i), i);
        }
        return j;
}

// After (hack because clang will unroll but not cmov, and g++ won't unroll)
template<unsigned int B, typename T>
static const T *inner_search(const T *base, const T x)
{
        if (B <= 1) {
                return base;
        }

        const unsigned int half = B / 2;
        const T *current = &base[half];
        return inner_search<B - half, T>((*current < x) ? current : base, x);
}

template<unsigned B, typename T, typename I, bool early_termination>
__attribute__((noinline))
I btree_array<B, T, I, early_termination>::search(const T x) {
	I j = n;
	I i = 0;
	while (i < n) {
                /* Last (partial block). */
                if (__builtin_expect(i + B >= n, 0)) {
                        const T *base = &a[i];
                        I m = n - i;

                        while (m > 1) {
                                I half = m / 2;
                                const T *current = &base[half];

                                base = (*current < x) ? current : base;
                                m -= half;
                        }

                        I ret = (*base < x) + base - a;
                        return (ret == n) ? j : ret;
                }

                const T *base = &a[i];
                const T *pred = inner_search<B, T>(base, x);
                unsigned int nth = (*pred < x) + pred - base;

                {
                        /* nth == B iff x > all values in block. */
                        const T current = base[nth % B];
                        I next = i + nth;

                        if (early_termination && current == x) {
                                return next;
                        }

                        j = (current >= x) ? next : j;
                }

		i = child(nth, i);
	}
	return j;
}

Breadth-first.cpp

// Eytzinger (breadth-first)
// Before
template<typename T, typename I>
I eytzinger_array<T,I>::search(const T &x) {
        I j = n;
        I i = 0;
        for (int d = 0; i < n; d++) {
                if (x < a[i]) {
                        j = i;
                        i = 2*i + 1;
                } else if (x > a[i]) {
                        i = 2*i + 2;
                } else {
                        return i;
                }
        }
        return j;
}

// After
template<typename T, typename I, bool early_termination>
__attribute__((noinline))
I eytzinger_array<T,I,early_termination>::search(const T x) {
	I j = n;
	I i = 0;
        while (i < n) {
                const T current = a[i];

                if (early_termination && current == x) {
                        return i;
                }

                j = (x <= current) ? i : j;
                i = (2 * i + 1) + (x > current);
	}

	return j;
}

Sorted array.cpp

// Sorted array.
//Before:
template<typename T, typename I>
I sorted_array<T,I>::search(const T &x) {
        I lo = 0;
        I hi = n;
        while (lo < hi) {
                I m = (lo + hi) / 2;
                if (x < a[m]) {
                        hi = m;
                } else if (x > a[m]) {
                        lo = m+1;
                } else {
                        return m;
                }
        }
        return hi;
}

//After: (That's a non-standard binary search, I should write about it)
template<typename T, typename I, bool early_termination>
__attribute__((noinline))
I sorted_array<T,I,early_termination>::search(const T x) {
	const T *base = a;
	I n = this->n;

        while (n > 1) {
                I half = n / 2;
                const T *ptr = &base[half];
                const T current = *ptr;

                if (early_termination && current == x) {
                        return ptr - a;
                }

                base = (current < x) ? ptr : base;
                n -= half;
        }

	return (*base < x) + base - a;
}

vEB.cpp

// van Emde Boas
// before
template<typename T, typename I>
I veb_array<T,I>::search(const T &x) {
        I rtl[MAX_H+1];
        I j = n;
        I i = 0;
        I p = 0;
        for (int d = 0; i < n; d++) {
                rtl[d] = i;
                if (x < a[i]) {
                        p <<= 1;
                        j = i;
                } else if (x > a[i]) {
                        p = (p << 1) + 1;
                } else {
                        return i;
                }
                i = rtl[d-s[d].h0] + s[d].m0 + (p&s[d].m0)*(s[d].m1);
        }
        return j;
}

// after
template<typename T, typename I, bool early_termination>
__attribute__((noinline))
I veb_array<T,I,early_termination>::search(const T &x) {
	I rtl[MAX_H+1];
	I j = n;
	I i = 0;
	I p = 0;
	for (int d = 0; i < n; d++) {
                const I h0 = h0s[d];
                const I h1_1 = h1_1s[d];
                const I m0 = ((I)2 << h0) - 1;

                const T current = a[i];
		rtl[d] = i;
                if (early_termination && current == x) {
                        return i;
                }

                j = (x <= current) ? i : j;
                p = (p << 1) + (x > current);
                I mask = p & m0;
		i = rtl[d - h0] + m0 + (mask << h1_1) - mask;
	}
	return j;
}