How fast can you make linear search?


I'm looking to optimize this linear search:

static int
linear (const int *arr, int n, int key)
        int i = 0;
        while (i < n) {
                if (arr [i] >= key)
        return i;

The array is sorted and the function is supposed to return the index of the first element that is greater or equal to the key. They array is not large (below 200 elements) and will be prepared once for a large number of searches. Array elements after the n-th can if necessary be initialized to something appropriate, if that speeds up the search.

No, binary search is not allowed, only linear search.

Edit: All my knowledge about this topic is now summarized in this blog post.


Well, you could use pointers...

static int linear(const int *array, int arraySize, int key) {
    int i;

    for(i = 0; i 
By : strager

loop backwards, this might be translated...

// loop backward

for (int i = arraySize - 1; i 

this might force vector instructions (suggested by Gman):

for (int i = 0; i 
By : Anycorn

This video can help you solving your question :)
By: admin