Tìm kiếm

/* Trả về chỉ số nếu tìm thấy, âm một nếu không.
   Kiểu trả về có dấu vì phải diễn tả được giá trị âm một. */
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;
}

size_t tim_het(const int *a, size_t n, int x, size_t *ket_qua, size_t co)
{
    size_t dem = 0;

    for (size_t i = 0; i < n; ++i)
        if (a[i] == x && dem < co)
            ket_qua[dem++] = i;

    return dem;
}

/* Khoảng đóng [lo, hi]. Cả hai đầu đều nằm trong vùng đang xét. */
long tim_nhi_phan(const int *a, size_t n, int x)
{
    if (n == 0) return -1;

    size_t lo = 0;
    size_t hi = n - 1;

    while (lo <= hi) {
        size_t mid = lo + (hi - lo) / 2;

        if (a[mid] == x)
            return (long)mid;

        if (a[mid] < x)
            lo = mid + 1;
        else {
            if (mid == 0) break;     /* tránh trừ dưới 0 với size_t */
            hi = mid - 1;
        }
    }

    return -1;
}

/* Khoảng nửa mở [lo, hi). Đầu hi KHÔNG nằm trong vùng xét.
   Cách này tránh hẳn phép trừ nên không có bẫy nào. */
long tim_nhi_phan2(const int *a, size_t n, int x)
{
    size_t lo = 0;
    size_t hi = n;              /* n chứ không phải n - 1 */

    while (lo < hi) {           /* dấu bé hơn chứ không phải bé hơn hoặc bằng */
        size_t mid = lo + (hi - lo) / 2;

        if (a[mid] == x)  return (long)mid;
        if (a[mid] <  x)  lo = mid + 1;
        else              hi = mid;      /* không có phép trừ */
    }

    return -1;
}

/* Trả về vị trí đầu tiên mà a[i] >= x. Nếu x lớn hơn mọi phần tử thì trả về n.
   Đây là công cụ để chèn giữ thứ tự, hoặc đếm số phần tử nhỏ hơn x. */
size_t vi_tri_chen(const int *a, size_t n, int x)
{
    size_t lo = 0, hi = n;

    while (lo < hi) {
        size_t mid = lo + (hi - lo) / 2;

        if (a[mid] < x) lo = mid + 1;
        else            hi = mid;
    }

    return lo;
}

size_t mid = (lo + hi) / 2;      /* cách viết trực giác, nhưng có thể tràn */
size_t mid = lo + (hi - lo) / 2; /* cách viết đúng */

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

static int so_sanh_int(const void *x, const void *y)
{
    int a = *(const int *)x;
    int b = *(const int *)y;

    return (a > b) - (a < b);      /* an toàn, không bị tràn như a - b */
}

int main(void)
{
    int a[] = { 2, 5, 8, 12, 16, 23, 38, 56, 72, 91 };
    size_t n = sizeof a / sizeof a[0];
    int can_tim = 23;

    int *p = bsearch(&can_tim, a, n, sizeof a[0], so_sanh_int);

    if (p != NULL)
        printf("Tim thay tai chi so %td\n", p - a);
    else
        printf("Khong tim thay\n");

    return 0;
}