5 ms·

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.

• jcs 2mo ago
  [dead]
• pkhuong 2mo ago
  Regardless of the array's size, the expected win from early exit on random keys is a constant number of iterations.