If the system doesn't do the sorting and your program doesn't do the sorting, who does it? The vacuum?

There probably is a solution. The point, however, is that the solution cannot use an algorithm that requires the data to be sorted first, because the data isn't sorted and sorting it is prohibited by the complexity requirement.

Okay, let's consider this simple example. A device that measures some variable, say temperature, writes the current value to a file ten times a second. Every day, the data is collected and fed to a program to analyze. The program needs to perform an operation on the data that requires the data to be sorted by value. But the data is sorted chronologically, not by value. Then the program does the sorting.

I'm not saying that. An algorithm that has a prerequisite cannot be used directly when that prerequisite isn't met. Therefore the algorithm used becomes just the second part of the large algorithm (the program), where the first part is meeting the prerequisites for the second part. The complexity of the whole program is the sum of the complexities of all its elements.

If you have unsorted data, your program cannot only consist of the binary search algorithm. Your program then becomes sorting plus binary search. O(nlogn + logn) = O(nlogn). That's my whole point. Then obviously there is no point using binary search if you only need to do it a constant number of times per one sort (unless that constant is very big). Your program cannot have any prerequisites that the input doesn't offer.