Dans le programme C, utilisez un algorithme de recherche binaire pour rechercher des nombres rationnels sans utiliser l'arithmétique à virgule flottante

Dans ce problème, on nous donne un tableau trié de nombres rationnels. Nous devons utiliser un algorithme de recherche binaire pour rechercher un élément donné de ce tableau de nombres rationnels sans utiliser d'opérations à virgule flottante.

Les nombres rationnels sont des nombres exprimés sous la forme p/q, où p et q sont tous deux des nombres entiers. Par exemple, ⅔, ⅕. La

Recherche binaire est une technique de recherche qui trouve des éléments en regardant au milieu d'un tableau.

Utilisé pour rechercher des éléments dans un tableau trié de nombres rationnels à l'aide de la recherche binaire, où les opérations en virgule flottante ne sont pas autorisées. Nous comparerons le numérateur et le dénominateur pour savoir quel élément est le plus grand ou quel élément est celui à trouver.

Exemple

Créons un programme pour cela,

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

sortie

Element found at index 2

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!