Verwenden Sie in einem C-Programm den binären Suchalgorithmus, um rationale Zahlen zu suchen, ohne Gleitkomma-Arithmetik zu verwenden

In diesem Problem erhalten wir eine sortierte Reihe rationaler Zahlen. Wir müssen einen binären Suchalgorithmus verwenden, um nach einem bestimmten Element dieses Arrays rationaler Zahlen zu suchen, ohne Gleitkommaoperationen zu verwenden.

Rationale Zahlen sind Zahlen, die in der Form p/q ausgedrückt werden, wobei p und q beide ganze Zahlen sind. Zum Beispiel ⅔, ⅕.

Binäre Suche ist eine Suchtechnik, die Elemente findet, indem sie in der Mitte eines Arrays sucht.

Wird verwendet, um Elemente in einem sortierten Array rationaler Zahlen mithilfe der binären Suche zu finden, wobei Gleitkommaoperationen nicht zulässig sind. Wir vergleichen Zähler und Nenner, um herauszufinden, welches Element größer ist bzw. welches Element dasjenige ist, das gefunden werden soll.

Beispiel

Lassen Sie uns dafür ein Programm erstellen,

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

Ausgabe

Element found at index 2

Das obige ist der detaillierte Inhalt vonVerwenden Sie in einem C-Programm den binären Suchalgorithmus, um rationale Zahlen zu suchen, ohne Gleitkomma-Arithmetik zu verwenden. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!