Tìm nhị phân

#include <stddef.h>

/* Tìm x trong mảng ĐÃ SẮP TĂNG DẦN.
   Trả về chỉ số một phần tử bằng x, hoặc n nếu không có.

   Bất biến: nếu x có trong a thì nó nằm trong nửa khoảng [lo, hi). */
size_t tim_nhi_phan(const int *a, size_t n, int x)
{
    size_t lo = 0;
    size_t hi = n;              /* hi nằm NGOÀI khoảng */

    while (lo < hi) {
        size_t giua = lo + (hi - lo) / 2;      /* KHÔNG viết (lo + hi) / 2 */

        if      (a[giua] == x) return giua;
        else if (a[giua] <  x) lo = giua + 1;  /* loại cả a[giua] */
        else                   hi = giua;      /* giua đã nằm ngoài, loại đúng */
    }

    return n;
}

/* Biên trái: chỉ số ĐẦU TIÊN có a[i] >= x.
   Bằng n nếu mọi phần tử đều nhỏ hơn x.
   Tương đương lower_bound của C++. */
size_t bien_trai(const int *a, size_t n, int x)
{
    size_t lo = 0, hi = n;

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

        if (a[giua] < x) lo = giua + 1;      /* a[giua] chắc chắn không đủ */
        else             hi = giua;          /* a[giua] có thể là đáp án */
    }

    return lo;
}

/* Biên phải: chỉ số ĐẦU TIÊN có a[i] > x.
   Tương đương upper_bound của C++. */
size_t bien_phai(const int *a, size_t n, int x)
{
    size_t lo = 0, hi = n;

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

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

    return lo;
}

/* Đếm số phần tử bằng x, chỉ hai lần tìm nhị phân. */
size_t dem_bang(const int *a, size_t n, int x)
{
    return bien_phai(a, n, x) - bien_trai(a, n, x);
}

/* Có x trong mảng không */
int co_mat(const int *a, size_t n, int x)
{
    size_t i = bien_trai(a, n, x);

    return i < n && a[i] == x;
}

#include <stdio.h>

int main(void)
{
    int    a[] = { 10, 20, 20, 20, 30, 40, 40, 50 };
    size_t n   = sizeof a / sizeof a[0];

    printf("mang: ");

    for (size_t i = 0; i < n; ++i) printf("%d ", a[i]);

    printf("\n\n%6s %10s %10s %8s %8s\n",
           "x", "bien_trai", "bien_phai", "so luong", "co mat");

    int thu[] = { 5, 10, 20, 25, 40, 50, 99 };

    for (size_t k = 0; k < sizeof thu / sizeof thu[0]; ++k) {
        int x = thu[k];

        printf("%6d %10zu %10zu %8zu %8d\n",
               x, bien_trai(a, n, x), bien_phai(a, n, x),
               dem_bang(a, n, x), co_mat(a, n, x));
    }

    return 0;
}

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

/* Hàm so sánh: âm nếu a trước b, 0 nếu bằng, dương nếu a sau b.
   Cùng hợp đồng với qsort, xem Bài 13.6. */
static int so_sanh_int(const void *pa, const void *pb)
{
    int a = *(const int *)pa;
    int b = *(const int *)pb;

    return (a > b) - (a < b);      /* KHÔNG viết a - b, sẽ tràn */
}

int main(void)
{
    int    a[] = { 10, 20, 30, 40, 50, 60, 70, 80 };
    size_t n   = sizeof a / sizeof a[0];
    int    x   = 60;

    int *p = bsearch(&x, a, n, sizeof *a, so_sanh_int);

    if (p != NULL)
        printf("thay %d tai chi so %td\n", *p, p - a);
    else
        printf("khong thay %d\n", x);

    return 0;
}

#include <stdio.h>

/* Bài toán: n gói kẹo, gói thứ i có a[i] viên.
   Chia cho k đứa trẻ, mỗi đứa nhận kẹo từ MỘT gói duy nhất,
   và mọi đứa phải nhận cùng số viên. Không được ghép hai gói.
   Hỏi mỗi đứa nhận nhiều nhất bao nhiêu viên. */

/* Vị từ đơn điệu: với v viên mỗi đứa, chia đủ cho k đứa không.
   Nếu chia đủ với v thì cũng chia đủ với mọi giá trị nhỏ hơn v,
   nên hàm này đơn điệu GIẢM theo v. */
static int du_cho(const long *a, size_t n, long v, long k)
{
    if (v <= 0) return 1;

    long tong = 0;

    for (size_t i = 0; i < n; ++i) {
        tong += a[i] / v;

        if (tong >= k) return 1;      /* dừng sớm, tránh tràn */
    }

    return 0;
}

/* Tìm v lớn nhất mà du_cho vẫn đúng. */
long chia_keo(const long *a, size_t n, long k)
{
    long lo = 0;                       /* luôn đủ */
    long hi = 0;                       /* tìm cận trên */

    for (size_t i = 0; i < n; ++i)
        if (a[i] > hi) hi = a[i];

    ++hi;                              /* hi chắc chắn KHÔNG đủ */

    /* Bất biến: du_cho(lo) đúng, du_cho(hi) sai. */
    while (hi - lo > 1) {
        long giua = lo + (hi - lo) / 2;

        if (du_cho(a, n, giua, k)) lo = giua;
        else                       hi = giua;
    }

    return lo;
}

int main(void)
{
    long   a[] = { 12, 8, 5, 20, 3 };
    size_t n   = sizeof a / sizeof a[0];

    for (long k = 1; k <= 8; ++k)
        printf("k = %ld  ->  moi dua nhan %ld vien\n", k, chia_keo(a, n, k));

    return 0;
}