Binary search in an ordered array with N keys uses no more than
lgN + 1 compares for a search (successful or not).
However, inserting a new key into an ordered array of size N uses ~2N array access in the worst case,
so inserting N keys into an initially empty table uses ~N-square array accesses in the worst case.
