What is the most efficient way to find elements in an unsorted list?

Given an unsorted list in an array, will it necessarily take at least linear time to 开发者_JAVA百科find the number of elements smaller than x? If so, why?

---

Yes, you would need to examine every number at least once to know if it is less than a specified threshold. If the numbers are not sorted there is nothing you can infer about them.

---

Yes you need at least linear time. There is no way to know whether an element is smaller than x without checking it, so you have to check every element once.

If you sorted it first, then you could stop as soon as an element was greater than x.

---

If you are allowing for an unlimited number of processors you can solve the problem in near constant time, assumming concatenating of the results is fast: Just split the array in chunks of fixed size and process each chunk on a separate processor.

If we are talking about a single processor I'd say you need linear time:

• you need to inspect each element and if it fits the predicate put it in the result.
• sorting or similar won't help, because again you have to inspect each element at least once.