Tìm tuyến tính

#include <stddef.h>

/* Trả về chỉ số phần tử đầu tiên bằng x, hoặc -1 nếu không có. */
long tim_tuyen_tinh(const int *a, size_t n, int x)
{
    for (size_t i = 0; i < n; ++i)
        if (a[i] == x)
            return (long)i;

    return -1;
}

/* Biến thể 1: chỉ số, quy ước trả về n */
size_t tim_chi_so(const int *a, size_t n, int x);

/* Biến thể 2: con trỏ, quy ước trả về NULL */
int *tim_con_tro(int *a, size_t n, int x)
{
    for (size_t i = 0; i < n; ++i)
        if (a[i] == x) return &a[i];

    return NULL;
}

/* Biến thể 3: tổng quát cho mọi kiểu, giống lfind của POSIX */
void *tim_tong_quat(const void *khoa, const void *mang,
                    size_t n, size_t co,
                    int (*so_sanh)(const void *, const void *))
{
    const char *p = mang;

    for (size_t i = 0; i < n; ++i, p += co)
        if (so_sanh(khoa, p) == 0)
            return (void *)p;

    return NULL;
}

/* Mảng phải có ÍT NHẤT n+1 ô, ô thứ n dùng làm chỗ đặt lính gác.
   Hàm sửa a tạm thời rồi khôi phục, nên a không được là const. */
size_t tim_linh_gac(int *a, size_t n, size_t suc_chua, int x)
{
    if (suc_chua <= n) return n;      /* không có chỗ cho lính gác */

    int cuu = a[n];

    a[n] = x;                          /* đặt lính gác */

    size_t i = 0;

    while (a[i] != x) ++i;             /* KHÔNG cần kiểm i < n */

    a[n] = cuu;                        /* khôi phục */

    return i;                          /* i bằng n nghĩa là không tìm thấy */
}

#include <stdio.h>
#include <stdlib.h>

static long dem;

static long tim_dem(const int *a, long n, int x)
{
    for (long i = 0; i < n; ++i) {
        ++dem;

        if (a[i] == x) return i;
    }

    return -1;
}

int main(void)
{
    const long n = 10000;
    int       *a = malloc((size_t)n * sizeof *a);

    if (a == NULL) return 1;

    for (long i = 0; i < n; ++i) a[i] = (int)i;

    srand(2024);

    /* Tìm phần tử chắc chắn có */
    dem = 0;

    for (long k = 0; k < 100000; ++k) tim_dem(a, n, rand() % (int)n);

    printf("tim thay     : %.1f phep so sanh TB, ly thuyet %.1f\n",
           (double)dem / 100000.0, (n + 1) / 2.0);

    /* Tìm phần tử chắc chắn không có */
    dem = 0;

    for (long k = 0; k < 100000; ++k) tim_dem(a, n, -1);

    printf("khong tim thay: %.1f phep so sanh TB, ly thuyet %ld\n",
           (double)dem / 100000.0, n);

    free(a);

    return 0;
}