You can search N objects in less than O(N) time if you have a way of testing multiple objects at once. Pre-sorting is one way to obtain this capability, but it's only one of many. Often the capability comes from the problem domain itself (or, more accurately, how you model time in your problem domain). In debugging, "one run of the program" often decently approximates a constant unit of time, and you can (theoretically) bisect once per run, giving you the ability to search without an explicit presort. In the wolf analogy, your ability to roughly determine which direction the wolf call is coming from does the same thing.

In both cases you could argue that you are "cheating" because there is a computational process of some kind doing at least O(N) work each time (the computer in the debugging example, the universe in the wolf example), giving O(NlnN)+ overall, strictly worse than an O(N) linear search. However, you have to ask yourself in this case if it makes sense to equate the time taken by the computer/universe to run one unit of its computation with the time taken to run one unit of your* search, and in many cases it doesn't. In the end it's just a model and it's up to you to choose what to measure, approximate, and exclude.

If someone tries to argue that there is fundamental philosophical truth that makes one model better than the other, start digging down into the physics of the CPU -- how much O(N^N) quantum computation did the universe have to do in order to bring you a single CPU cycle? God only knows, but the time it takes is nearly constant, so it makes sense to ignore. Even the most hard-core theoretical algorithms expert is just as "guilty" of this kind of approximation as you are :-)

Binary search is looking for a value. Wolf-fencing is looking for a side-effect of that value.

As per analogy, you're not checking an animal in Alaska to see if it is a wolf, you are waiting till the wolf howls (side effect of wolf-existence) then focusing your efforts in that area.

So you can't really use wolf-fencing to say... find a number in an array; it makes no sense.

I like this explanation ;)

So apply a binary search to an effect instead of a value.