浮動小数点演算を使わずに有理数の配列を二分探索するCプログラム

この問題では、ソート済みの有理数の配列が与えられ、その中から指定した要素を浮動小数点演算を一切使わずに二分探索アルゴリズムで検索します。

有理数とは

有理数とは、2つの整数 p と q を用いて p/q の形で表される数のことです。例として、⅔ や ⅕ などが挙げられます。ここで p は分子、q は分母と呼ばれます。

二分探索とは

二分探索（バイナリサーチ）は、ソートされた配列から目的の要素を効率的に見つける検索手法です。配列の中央の要素と検索対象を比較し、大小関係に応じて探索範囲を半分に絞り込むことを繰り返します。計算量は O(log n) と非常に効率的です。

浮動小数点演算を使わない比較方法

通常、有理数を比較するには p/q を実際に割り算して実数値として評価しますが、これには浮動小数点演算が必要です。そこで本プログラムでは、交叉乗算（クロス乗算）という手法を使います。

2つの有理数 a = p1/q1 と b = p2/q2 を比較する場合：

• p1 × q2 == q1 × p2 ならば、a と b は等しい
• p1 × q2 > q1 × p2 ならば、a は b より大きい
• p1 × q2 < q1 × p2 ならば、a は b より小さい

この方法なら、除算を行わずに整数の乗算だけで正確な比較が可能です。

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;   // a の方が大きい
    return -1;      // b の方が大きい
}

// 二分探索の再帰的実装
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

コードの解説

• Rational構造体：分子 p と分母 q を持つ構造体で、有理数を表現します。
• compare関数：交叉乗算により、浮動小数点演算なしで2つの有理数の大小を判定します。
• binarySearch関数：中央の要素と検索対象を compare 関数で比較し、探索範囲を再帰的に半分に絞り込みます。要素が見つかればそのインデックスを、見つからなければ -1 を返します。

このように、交叉乗算のテクニックを用いることで、精度低下や丸め誤差のリスクがある浮動小数点演算を避けながら、有理数の配列に対して高速かつ正確な二分探索を実現できます。