This can happen in very unintuitive places. For example, in Java, array.size() reads from the same cache line as the beginning of the array. If you're partitioning an array processing routine for many cores, you should not call array.size() to avoid very expensive synchronization.
You can also think about it as a sort of reductio ad absurdum: Assume that the array is actually already sorted and you use a sorting algorithm with O(n) complexity for already sorted data. In this ideal case you'd need to do n (for sorting) + log n (binary search) predictable operations. For linear search you'd only need to n operations of the same type. In practice you'd need to do n log n operations for sorting, I don't think you can avoid unpredictable branches, and instead of just loading elements sometimes you'll move them around.
When dealing with small arrays (like the example of 0-250 integers, ie. less than 1 kilobyte), the figures are around 20-120 nanoseconds. In other words, the difference is around one main memory reference ("cache miss") between the best and the worst case.
While this is somewhat interesting, the lesson to take home should be that most of the time, smart memory usage is more important than what the CPU executes. Warming up the caches (e.g. __builtin_prefetch) is as efficient an optimization as rewriting and unrolling the entire loop and should be done first. If the caches are warm and the search is still the bottleneck, then it's time to consider the other optimizations.