Is this true even for small lists without many duplicates?
You may be able to compromise and use an ordered list and a binary search.
You may be able to compromise and use an ordered list and a binary search.