Re: A question: Is 200,000 element array worth sorting and search?

>CBFalconer said:
>>    for (i = 0; i <= 200000; i++) {

In article <7dmdnfY00vue8oPVRVnyuQA@[EMAIL PROTECTED]
>
Richard Heathfield  <rjh@[EMAIL PROTECTED]
> wrote:
>Rookie error...

>>       if (a[i] == item) break;
>>    }
>>    if ((i <= 200000) && (a[i] == item)) return i;

>...repeated.

Given the idea that the array has exactly 200000 elements, anyway.
In reality the "occupied size" would presumably be a variable.

In any case, this misses out on a handy trick that can be used when
the array has enough room.  When a[] is the array to be searched and
n is "occupied size", if a[n] can be overwritten, one can use:

    a[n] = item;
    for (i = 0; a[i] != item; i++)
        continue;

This removes one test (i < n) from the loop, and yet is guaranteed
to terminate the loop.  Then one need only apply the "i < n" test
afterward.

(Also, even with the "i < n" test in the loop, there is no need to
re-test a[i]==item afterward.)

In reality, the original question is not very well formed, for
reasons that others have touched on.  If the options include "sorting
the array", one has to consider how often the searches will happen
compared to the sort, and whether modifications to the array can
be done in ways that maintain the sorted order.  If the array *is*
sorted, we can use binary or even interpolative searches rather
than linear searches.  (Binary search is O(log n) and interpolative
search is O(log log n), in the mythical average case at least.)
-- 
In-Real-Life: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W)  +1 801 277 2603
email: gmail (figure it out)      http://web.torek.net/torek/index.html