How many needles you're looking for, and at what frequency (if ever again) you're going to need to run the search. Building any alternative data structure from

How many needles you're looking for, and at what frequency (if ever again) you're going to need to run the search. Building any alternative data structure from an unsorted array will require O(n) time. If you only need to find something once, then a O(n) linear scan time is optimal.