Randomized Binary and Tree Search under Pressure

Agustín Caracci, Christoph Dürr, José Verschae

We study a generalized binary search problem on the line and general trees. On the line (e.g., a sorted array), binary search finds a target node in $O(\log n)$ queries in the wors…