  This work studies the problem of 2-dimensional searching for the 3-sided
range query of the form $[a, b]\times (-\infty, c]$ in both main and external
memory, by considering a variety of input distributions. We present three sets
of solutions each of which examines the 3-sided problem in both RAM and I/O
model respectively. The presented data structures are deterministic and the
expectation is with respect to the input distribution.
