Detailed mathematical approach

Problem Summary

We consider successful search in a sorted array of \(n\) distinct keys, where the target key is chosen uniformly from those \(n\) keys. Two search rules are compared:

$B(n)=\text{expected comparisons when each recursive step probes the midpoint},$

$R(n)=\text{expected comparisons when each recursive step chooses its pivot uniformly at random}.$

The problem asks for the difference \(R(n)-B(n)\) at \(n=10^{10}\). A direct simulation would be pointless, so the solution derives closed forms for both expectations and evaluates them numerically.

Mathematical Approach

Both expectations come from the shape of the search tree induced by the rule used at each step. The midpoint rule produces a nearly complete binary tree, while the random-pivot rule leads to the same average successful-search cost as a random binary search tree.

Step 1: Deterministic midpoint search gives a complete-level count

Let \(h=\lfloor \log_2 n \rfloor\). Then the first \(h\) levels of the induced decision tree contain

$1+2+\cdots+2^{h-1}=2^h-1$

keys. Write

$r=n-(2^h-1),\qquad 1\le r\le 2^h.$

All levels \(0,1,\dots,h-1\) are full, and the remaining \(r\) keys sit on depth \(h\). A key at depth \(d\) needs \(d+1\) comparisons, so the total number of comparisons over all \(n\) possible targets is

$S_B(n)=\sum_{d=0}^{h-1}(d+1)2^d+(h+1)r.$

Using the finite-sum identity

$\sum_{d=0}^{h-1}(d+1)2^d=(h-1)2^h+1,$

we obtain

$S_B(n)=(h+1)n-2^{h+1}+(h+2),$

hence

$\boxed{B(n)=\frac{S_B(n)}{n}=(h+1)-\frac{2^{h+1}-(h+2)}{n}.}$

Step 2: Randomized search satisfies a clean recurrence

For the randomized rule, let the current pivot have rank \(k\in\{1,\dots,n\}\), chosen uniformly, and let the target have rank \(t\in\{1,\dots,n\}\), also uniform. One comparison is paid immediately.

If \(t=k\), the search stops. If \(t<k\), the next subproblem has size \(k-1\). If \(t>k\), the next subproblem has size \(n-k\). Averaging over all \(n^2\) pairs \((t,k)\) gives

$R(n)=1+\frac{1}{n^2}\sum_{k=1}^{n}\left((k-1)R(k-1)+(n-k)R(n-k)\right).$

Equal subproblem sizes appear symmetrically on the left and on the right, so this simplifies to

$\boxed{R(n)=1+\frac{2}{n^2}\sum_{i=1}^{n-1} i\,R(i).}$

This is exactly the same recurrence as the average successful-search cost in a random binary search tree.

Step 3: Solve the recurrence with a telescoping transformation

Multiply the recurrence by \(n^2\):

$n^2R(n)=n^2+2\sum_{i=1}^{n-1} i\,R(i).$

Write the same formula for \(n-1\), subtract, and rearrange:

$\frac{nR(n)}{n+1}=\frac{(n-1)R(n-1)}{n}+\frac{2n-1}{n(n+1)}.$

Now define

$A_n=\frac{nR(n)}{n+1}.$

Then

$A_n=A_{n-1}+\frac{2n-1}{n(n+1)}=A_{n-1}-\frac{1}{n}+\frac{3}{n+1}.$

Since \(R(1)=1\), we have \(A_1=\frac12\). Telescoping from \(2\) to \(n\) yields

$A_n=\frac12+\sum_{k=2}^{n}\left(-\frac{1}{k}+\frac{3}{k+1}\right)=2H_n+\frac{3}{n+1}-3,$

where

$H_n=\sum_{k=1}^{n}\frac1k$

is the \(n\)-th harmonic number. Substituting back gives the closed form

$\boxed{R(n)=2\frac{n+1}{n}H_n-3.}$

Step 4: Large \(n\) is handled through the harmonic asymptotic

For the actual target size, computing \(H_n\) term by term is unnecessary. The implementation uses the Euler-Maclaurin expansion

$H_n=\log n+\gamma+\frac{1}{2n}-\frac{1}{12n^2}+\frac{1}{120n^4}+O(n^{-6}),$

where \(\gamma\) is the Euler-Mascheroni constant. At \(n=10^{10}\), the omitted terms are far smaller than the requested eight decimal places, so the approximation is more than sufficient.

The final quantity is therefore

$\boxed{\Delta(n)=R(n)-B(n)=2\frac{n+1}{n}H_n-3-\left((h+1)-\frac{2^{h+1}-(h+2)}{n}\right),\qquad h=\lfloor\log_2 n\rfloor.}$

Worked Example: \(n=6\)

Here \(h=\lfloor\log_2 6\rfloor=2\) and \(r=6-(2^2-1)=3\). The deterministic search tree has one key at depth \(0\), two keys at depth \(1\), and three keys at depth \(2\). Hence

$S_B(6)=1\cdot1+2\cdot2+3\cdot3=14,\qquad B(6)=\frac{14}{6}=\frac73=2.333333\ldots$

For the randomized rule,

$H_6=1+\frac12+\frac13+\frac14+\frac15+\frac16=\frac{49}{20},$

so

$R(6)=2\cdot\frac76\cdot\frac{49}{20}-3=\frac{163}{60}=2.716666\ldots$

Therefore

$R(6)-B(6)=\frac{163}{60}-\frac73=\frac{23}{60}=0.383333\ldots,$

which matches the checkpoint used by the implementation.

How the Code Works

The C++, Python, and Java implementations follow the same numerical plan. First, they evaluate \(B(n)\) directly from the closed form, obtaining \(\lfloor\log_2 n\rfloor\) with integer bit-length logic instead of recursive simulation.

Next, they evaluate \(H_n\). For \(n\le 10^6\), the harmonic number is summed exactly as \(\sum_{k=1}^{n}1/k\), which is useful for small checkpoints and keeps the formula accurate on small inputs. For larger \(n\), they switch to the asymptotic series above and use the Euler-Mascheroni constant explicitly.

With \(H_n\) available, they compute \(R(n)=2\frac{n+1}{n}H_n-3\), subtract \(B(n)\), and print the result with eight digits after the decimal point. The C++ implementation also verifies the \(n=6\) checkpoint before evaluating the main case.

Complexity Analysis

The implementation is piecewise. On the exact harmonic-sum branch, the running time is \(O(n)\) and the memory usage is \(O(1)\). On the asymptotic branch, which is the one used for the actual input \(n=10^{10}\), both time and memory are \(O(1)\). In practice the Project Euler instance is handled by a constant amount of floating-point arithmetic.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=527
2. Binary search: Wikipedia — Binary search algorithm
3. Harmonic number: Wikipedia — Harmonic number
4. Binary search tree: Wikipedia — Binary search tree
5. Euler-Maclaurin formula: Wikipedia — Euler-Maclaurin formula