How fast can you make linear search?

Question!

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)
                        break;
                ++i;
        }
        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.



Answers

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