When Does Binary Search Apply?

Binary search is taught on sorted arrays, but its real applicability is wider — and subtler.

Your answer should cover:

1. The actual precondition for binary search (hint: it's about a predicate, not about "the array is sorted").
2. An example of binary searching something that isn't a sorted array — e.g. "binary search on the answer". Sketch how it works.
3. Why binary search on a linked list is pointless even if the list is sorted.
4. The classic implementation pitfalls (give at least two and how to avoid them).