[ww520]

For small arrays that can fit in L1 cache, it's ok to do more loops. For bigger arrays, cache miss could remove all the gains.

[pkhuong]

Regardless of the array's size, the expected win from early exit on random keys is a constant number of iterations.