Tìm kiếm nhị phân cho số hữu tỉ không dùng số thực trong C

Cho một mảng đã sắp xếp các số hữu tỉ. Nhiệm vụ là tìm một phần tử cho trước bằng thuật toán tìm kiếm nhị phân mà không sử dụng phép toán số thực (floating point).

Số hữu tỉ là số biểu diễn dưới dạng p/q với p, q là số nguyên. Ví dụ: ⅔, ⅕.

Tìm kiếm nhị phân là kỹ thuật tìm kiếm bằng cách chia đôi mảng để tìm phần tử.

Để tìm phần tử trong mảng số hữu tỉ đã sắp xếp mà không dùng số thực, ta so sánh tử số và mẫu số để xác định phần tử nào lớn hơn hoặc bằng phần tử cần tìm.

Mã nguồn C

#include <stdio.h>

struct Rational {
    int p;
    int q;
};

int compare(struct Rational a, struct Rational b) {
    if (a.p * b.q == a.q * b.p)
        return 0;
    if (a.p * b.q > a.q * b.p)
        return 1;
    return -1;
}

int binarySearch(struct Rational arr[], int l, int r, struct Rational x) {
    if (r >= l) {
        int mid = l + (r - l) / 2;
        if (compare(arr[mid], x) == 0) return mid;
        if (compare(arr[mid], x) > 0)
            return binarySearch(arr, l, mid - 1, x);
        return binarySearch(arr, mid + 1, r, x);
    }
    return -1;
}

int main() {
    struct Rational arr[] = {{1, 4}, {2, 3}, {3, 2}, {7, 2}};
    struct Rational x = {3, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Phần tử tìm thấy tại chỉ số %d", binarySearch(arr, 0, n - 1, x));
    return 0;
}

Kết quả

Phần tử tìm thấy tại chỉ số 2