linear_4.c

linear_4.c

// https://schani.wordpress.com/2010/04/30/linear-vs-binary-search/

static int
linear_4 (const int *arr, int n, int key) {
        int i = 0;
        while (i + 3 < n) {
                if (arr [i + 0] >= key) return i + 0;
                if (arr [i + 1] >= key) return i + 1;
                if (arr [i + 2] >= key) return i + 2;
                if (arr [i + 3] >= key) return i + 3;
                i += 4;
        }
        while (i < n) {
                if (arr [i] >= key)
                        break;
                ++i;
        }
        return i;
}