在C程式中，使用二分查找演算法來搜尋有理數，而不使用浮點數算術

在這個問題中，我們得到了一個有理數的排序數組。我們必須使用二分搜尋演算法來搜尋該有理數數組的給定元素，而不使用浮點運算。

有理數是以 p/q 形式表示的數字，其中p 和 q 都是整數。例如，⅔、⅕。

二分搜尋是一種搜尋技術，透過尋找陣列的中間來找出元素。

用於尋找使用二分法搜尋有理數排序數組中的元素，其中不允許浮點運算。我們將比較分子和分母，以找出哪個元素較大或哪個元素是要找到的元素。

範例

讓我們為此建立一個程序，

#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

以上是在C程式中，使用二分查找演算法來搜尋有理數，而不使用浮點數算術的詳細內容。更多資訊請關注PHP中文網其他相關文章！