In C program, use binary search algorithm to search rational numbers without using floating point arithmetic

In this problem, we are given a sorted array of rational numbers. We have to use binary search algorithm to search for a given element of this array of rational numbers without using floating point operations.

Rational numbers are numbers expressed in the form p/q, where p and q are integers. For example, ⅔, ⅕.

Binary search is a search technique that finds elements by looking in the middle of an array.

is used to find elements in a sorted array of rational numbers using binary search, where floating point operations are not allowed. We will compare the numerator and denominator to find out which element is greater or which element is the one to be found.

Example

Let’s create a program for this,

#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));
}

Output

Element found at index 2

The above is the detailed content of In C program, use binary search algorithm to search rational numbers without using floating point arithmetic. For more information, please follow other related articles on the PHP Chinese website!