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.

Answer 1

1. Tell your boss you can make it 50% faster, but it will take 6 months, and some money.
2. Wait six months.
3. Buy new hardware.

Well, it makes about as much sense as a linear search through a sorted array!

(More seriously, can you give us some clues about why no binary search?)