that he wants you to do a binary lookup or equivalent (hash, BTree, etc) rather than scan a list.

You get a linear degradation in performance when you linearly scan a list, if the list has twice as many things it takes on average twice as long to do a lookup. You get a logarithmic degradation when you do a binary lookup.

That is he wants lookup time to scale like O(log(n)) rather than O(n).

Of course he may well completely misunderstand the performance characteristics of your system and why it looks like it does.

If he isn't technical, I'd guess that he is just repeating a magical invocation that someone else said, and he hopes it will make you do something useful.

Cheers,
Ben