Introduction

Standard binary search runs in O(log n) time, but micro-optimizations can significantly reduce the constant factor. Techniques include branchless comparisons, avoiding integer overflow in midpoint calculation, prefetching cache lines, using Eytzinger layout for cache-friendly access, and converting to a branchless conditional move. These optimizations matter in performance-critical code like database indexes, competitive programming, and real-time systems.

Standard Binary Search

1// Classic binary search — correct but not optimized
2int binary_search(int *arr, int n, int target) {
3    int lo = 0, hi = n - 1;
4    while (lo <= hi) {
5        int mid = lo + (hi - lo) / 2;  // Overflow-safe
6        if (arr[mid] == target) return mid;
7        else if (arr[mid] < target) lo = mid + 1;
8        else hi = mid - 1;
9    }
10    return -1;
11}

Optimization 1: Overflow-Safe Midpoint

The naive mid = (lo + hi) / 2 overflows when lo + hi exceeds INT_MAX:

1// BAD — overflows for large lo and hi
2int mid = (lo + hi) / 2;
3
4// GOOD — no overflow
5int mid = lo + (hi - lo) / 2;
6
7// ALSO GOOD — unsigned right shift (Java, C with unsigned types)
8int mid = (lo + hi) >>> 1;  // Java
9unsigned mid = ((unsigned)lo + (unsigned)hi) >> 1;  // C

In Java, the >>> operator performs unsigned right shift, which handles the overflow case correctly. This was a real bug in Java's Arrays.binarySearch that went undetected for years.

Optimization 2: Branchless Binary Search

Branch mispredictions are expensive on modern CPUs (10-20 cycle penalty). Binary search on random data has ~50% misprediction rate. A branchless version uses conditional moves (cmov):

1// Branchless binary search — uses conditional move
2int branchless_search(int *arr, int n, int target) {
3    int lo = 0;
4    while (n > 1) {
5        int half = n / 2;
6        // cmov: no branch, CPU selects value
7        lo += (arr[lo + half] < target) * half;
8        n -= half;
9    }
10    return (arr[lo] == target) ? lo : -1;
11}

The key insight is (arr[lo + half] < target) evaluates to 0 or 1, and multiplication replaces the branch. The compiler turns this into a cmov instruction.

1// Lower bound (first element >= target) — branchless
2int lower_bound(int *arr, int n, int target) {
3    int lo = 0;
4    while (n > 1) {
5        int half = n / 2;
6        lo += (arr[lo + half] < target) * half;
7        n -= half;
8    }
9    lo += (arr[lo] < target);
10    return lo;
11}

Optimization 3: Eytzinger Layout

Standard binary search has poor cache behavior — it accesses memory positions that are far apart. The Eytzinger layout rearranges array elements into a breadth-first order of an implicit binary tree:

1// Convert sorted array to Eytzinger layout
2void build_eytzinger(int *sorted, int *eytzinger, int n, int *idx, int k) {
3    if (k <= n) {
4        build_eytzinger(sorted, eytzinger, n, idx, 2 * k);      // Left child
5        eytzinger[k] = sorted[(*idx)++];
6        build_eytzinger(sorted, eytzinger, n, idx, 2 * k + 1);  // Right child
7    }
8}
9
10// Search in Eytzinger layout — no branches
11int eytzinger_search(int *ey, int n, int target) {
12    int k = 1;
13    while (k <= n) {
14        __builtin_prefetch(&ey[k * 16]);  // Prefetch ahead
15        k = 2 * k + (ey[k] < target);     // Branchless: left or right child
16    }
17    k >>= __builtin_ffs(~k);  // Find the answer node
18    return (ey[k] == target) ? k : -1;
19}

The Eytzinger layout stores the root at index 1, left child at 2k, and right child at 2k+1. This means successive comparisons access nearby memory addresses, improving cache hit rates by 2-3x for large arrays.

Optimization 4: Prefetching

Explicit prefetch hints tell the CPU to load cache lines before they are needed:

1int search_with_prefetch(int *arr, int n, int target) {
2    int lo = 0, hi = n - 1;
3    while (lo <= hi) {
4        int mid = lo + (hi - lo) / 2;
5        // Prefetch both possible next midpoints
6        __builtin_prefetch(&arr[(lo + mid) / 2]);
7        __builtin_prefetch(&arr[(mid + 1 + hi) / 2]);
8
9        if (arr[mid] < target) lo = mid + 1;
10        else if (arr[mid] > target) hi = mid - 1;
11        else return mid;
12    }
13    return -1;
14}

Prefetching is most effective for large arrays that do not fit in L2 cache (typically > 256KB of data).

Optimization 5: Compiler Hints and SIMD

1// Use __builtin_expect to hint the likely branch
2if (__builtin_expect(arr[mid] < target, 1)) {
3    lo = mid + 1;
4}
5
6// Ensure alignment for SIMD-friendly access
7int *arr __attribute__((aligned(64)));

For searching multiple targets simultaneously, SIMD instructions can process 4-16 comparisons in parallel using AVX2/AVX-512.

Benchmarking the Optimizations

Typical speedups over standard binary search for arrays of 10M integers:

Common Pitfalls

• Integer overflow in midpoint calculation: (lo + hi) / 2 overflows when both values are large. Always use lo + (hi - lo) / 2 or unsigned arithmetic. This was a real bug in the JDK's binary search for nearly a decade.
• Branchless code that the compiler undoes: Compilers may convert your branchless multiplication back into branches. Check the assembly output with gcc -S or Compiler Explorer (godbolt.org) to verify cmov instructions are generated.
• Eytzinger layout overhead for small arrays: The Eytzinger layout adds a preprocessing step (O(n) time and space) and complicates insertion. It only pays off for large, read-heavy arrays (thousands of elements or more) that are searched repeatedly.
• Prefetching too aggressively: Prefetching every iteration adds instruction overhead. Only prefetch when the array exceeds L2 cache size. Unnecessary prefetch instructions consume memory bandwidth and can slow down small-array searches.
• Micro-optimizing before profiling: These optimizations improve binary search by constant factors, not asymptotic complexity. If binary search is not the bottleneck (often the surrounding code dominates), these optimizations provide zero measurable improvement. Always profile first.

Summary

• Use lo + (hi - lo) / 2 to avoid integer overflow in midpoint calculation
• Branchless binary search with conditional moves (cmov) eliminates branch misprediction penalties
• Eytzinger layout rearranges array elements for cache-friendly access (2-3x speedup on large arrays)
• Prefetching upcoming cache lines reduces memory latency for arrays larger than L2 cache
• Combine techniques (Eytzinger + branchless + prefetch) for maximum throughput (3-5x over standard)
• Profile before optimizing — these techniques only matter when binary search is the actual bottleneck