Either use a sorted array, and perform binary search (if the dataset is static), or use a balanced search tree (if the set changes after it's build). Both can be build in O(n log n) time, with an O(log n) query time.

Of course, if you only have o(log n) (that's little-o) queries, it's faster to just do full scans, and leave the list unsorted.