โปรแกรม C ค้นหาเลข 유리수 (Rational Numbers) ด้วย Binary Search โดยไม่ใช้ Floating Point

ในปัญหานี้ เราได้รับอาร์เรย์ของเลขมีมี (rational numbers) ที่เรียงลำดับแล้ว และต้องค้นหาเลขเป้าหมายโดยใช้ Binary Search โดยห้ามใช้การคำนวณ floating point

เลขมีมี (Rational number) คือตัวเลขที่แสดงในรูป p/q โดยที่ p และ q เป็นจำนวนเต็ม เช่น ⅔, ⅕

Binary Search เป็นเทคนิคค้นหาที่ทำงานโดยหาจุดกึ่งกลางของอาร์เรย์เพื่อเปรียบเทียบกับค่าที่ต้องการ

สำหรับการค้นหาเลขมีมีในอาร์เรย์ที่เรียงลำดับโดยไม่ใช้ floating point เราจะเปรียบเทียบตัวเศษ (numerator) และตัวส่วน (denominator) เพื่อพิจารณาว่าตัวไหนมากกว่าหรือตรงกับค่าที่ค้นหา

ตัวอย่าง

#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("Element found at index %d", binarySearch(arr, 0, n-1, x));
}

ผลลัพธ์

Element found at index 2