I'm surprised that even the fastest implementation needs 20+ms to search a 1000-element array. I would expect even a linear search to finish within 1 or 2ms wit

I'm surprised that even the fastest implementation needs 20+ms to search a 1000-element array. I would expect even a linear search to finish within 1 or 2ms with such a small data set. How large are the array elements? How were the times measured? EDIT: Oh the time measured is the total of 1,000,000 random lookups? Nevermind my confusion then, that would certainly explain it.