Simple Problem but tough for me if i want it in linear time

[Steven D'Aprano]

On Sun, 15 Aug 2010 05:47:04 -0700, ChrisChia wrote:

> dataList = [a, b, c, ...]
> where a, b, c are objects of a Class X. In Class X, it contains
> self.name and self.number
> 
> If i wish to test whether a number (let's say 100) appears in one of the
> object, and return that object,
> is that only fast way of solving this problem without iterating through
> every object to see the number value?
> 
> dataList.__contains__ can only check my object instance name... 
> anyone can solve this in linear complexity?

If all you want is *linear* time, then simply iterating over the items 
will do the job:

for item in dataList:
    if item.number == 100:
        do_something_with(item)
        break


If you want *less* than linear time, then keep the list sorted and do a 
binary search, which gives you O(log N) time. Don't sort the list each 
time, because that's O(N*log N). Or use a dict, which gives you O(1) time.


-- 
Steven