Nice idea... I have taken it a notch further, by choosing which key to update based on that comparison, i.e.:
```
if (@TYPE@_LT(last_key_val, key_val)) {
    max_idx = arr_len;
} else {
    min_idx = 0;
    max_idx++;
}
```

Timing it shows a big boost for sorted needles, but a slight slowdown for purely random ones. I have put up results for arrays of floats [here](https://gist.github.com/jaimefrio/8704101#file-gistfile2-txt).

If you assume that the needles and the haystack are uniformly distributed over [0, 1], I think you can actually prove that you are going to be doing more comparisons on average.

The good thing is that the slowdown is always less than the speed-up over numpy 1.8. So from the point of view of a numpy 1.9 user everything would be faster, and sorted inputs would be much faster, nothing will slow down. Only we would know that we could improve some at the expense of others...