“Best algorithm ever”: binary search and an IOI gold

My coach Sergey Melnik — a really good teacher — kept insisting on one algorithm. Remember this one, he told us, it’s the best of all: it finds the answer precisely, it always works, and it’s fast. It was binary search — the version that finds the leftmost position:

function binary_search_leftmost(A, n, T):
    L := 0
    R := n
    while L < R:
        m := floor((L + R) / 2)
        if A[m] < T:
            L := m + 1
        else:
            R := m
    return L

I didn’t just memorise it — I fell in love with it, and made sure I understood exactly why it works and where its boundaries are. That’s where most people get binary search wrong: off by one, an infinite loop, the wrong side of the target.

At the International Olympiad in Informatics in 2002, the task Two Rods needed exactly that. Two rods — one horizontal, one vertical — are hidden on a grid, and you find them by asking whether a rectangle contains any part of them. The solution is binary search several times over: in one direction and the other, along the rows and then along the columns. I got a clean 100 points on it.

Yongin, Korea, 2002: three of the four members of Latvia’s team — Alexander Belov, Sergey Kozlovich and me (right).

At the olympiad you could order printouts of your programs, to sit and think with paper and a pen. I ordered one of that solution, wrote on it “Thank you, Sergey Melnik, for this algorithm we learned”, brought it home to Riga and gave it to him.

Twenty years later I still posted it with one caption: best algorithm ever.

Back in Riga: the reception for Latvia’s olympiad medallists after IOI 2002.

2002: congratulations from the Mayor of Riga, Gundars Bojārs.