在C程序中不使用浮点算术对有理数进行二进制搜索

Z时代
2024-01-10
分类：综合

在这个问题上，我们得到了有理数的排序数组。并且我们必须使用二进制搜索算法针对该有理数数组搜索给定元素，而无需使用浮点算法。

甲有理数的形式为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));
}