Least expensive equality search for small unsorted arrays

Question

What is the most efficient method, in terms of execution time, to search a small array of about 4 to 16 elements, for an element that is equal to what you're searching for, in C++? The element being searched for is a pointer in this case, so it's relatively small.

(My purpose is to prevent points in a point cloud from creating edges with points that already share an edge with them. The edge array is small for each point, but there can be a massive number of points. Also, I'm just curious too!)

Answer 1

Your best bet is to profile your specific application with a variety of mechanisms and see which performs best.

I suspect that given it's unsorted a straight linear search will be best for you. If you're able to pre-sort the array once and it updates infrequently or never, you could pre-sort and then use a binary search.

Answer 2

Try a linear search; try starting with one or more binary chop stages. The former involves more comparisons on average; the latter has more scope for cache misses and branch mispredictions, and requires that the arrays are pre-sorted.

Only by measuring can you tell which is faster, and then only on the platform you measured on.

Answer 3

If you have to do this search more than once, and the array doesn't change often/at all, sort it and then use a binary search.