Cost

Logarithmic time

Each step throws away a fraction of what remains, so a million sorted elements is only about twenty comparisons.

Logarithmic time means each step shrinks the problem by a fraction, not by one element. Binary search is the picture you can draw: look in the middle, throw away half, repeat. A million sorted numbers takes on the order of twenty comparisons. Adding another million does not add another million steps.

You will also meet log n as a height. A balanced tree has height about log n, so a walk from the root to a leaf is logarithmic. A tree that has collapsed into a straight line has height n, and the same walk becomes linear. The algorithm did not change. The shape of the data did.

The bugs in logarithmic code are usually off by one, not "the idea was too slow". Keep a sentence that says where the answer is still allowed to be, and move the bounds so that sentence stays true.