If you break this down into one or two additional levels of subdirectories, it can become a log(N) function instead.

With one layer of subdirectories, it'll become the square root of N. With two layers, it'll become the fourth root of N.

You'd need Ω(log N) layers of directories to bring it down to O(log N) search time.