有理数表示为p/qb，例如2/3。给定有理数的排序数组，介绍如何使用二进制搜索来搜索元素。不允许使用浮点运算。
null
例子：
Input: arr[] = {1/5, 2/3, 3/2, 13/2} x = 3/2Output: Found at index 2
我们强烈建议您尽量减少浏览器，并先自己尝试。 为了比较两个有理数p/q和r/s，我们可以比较p*s和q*r。
C++
// C++ program for Binary Search for // Rational Numbers without using // floating point arithmetic #include <iostream> using namespace std; struct Rational { int p; int q; }; // Utility function to compare two // Rational numbers 'a' and 'b'. // It returns // 0 --> When 'a' and 'b' are same // 1 --> When 'a' is greater //-1 --> When 'b' is greater int compare( struct Rational a, struct Rational b) { // If a/b == c/d then a*d = b*c: // method to ignore division if (a.p * b.q == a.q * b.p) return 0; if (a.p * b.q > a.q * b.p) return 1; return -1; } // Returns index of x in arr[l..r] if // it is present, else returns -1. It // mainly uses Binary Search. int binarySearch( struct Rational arr[], int l, int r, struct Rational x) { if (r >= l) { int mid = l + (r - l) / 2; // If the element is present at the middle itself if (compare(arr[mid], x) == 0) return mid; // If element is smaller than mid, then it can // only be present in left subarray if (compare(arr[mid], x) > 0) return binarySearch(arr, l, mid - 1, x); // Else the element can only be present in right // subarray return binarySearch(arr, mid + 1, r, x); } return -1; } // Driver code int main() { struct Rational arr[] = { { 1, 5 }, { 2, 3 }, { 3, 2 }, { 13, 2 } }; struct Rational x = { 3, 2 }; int n = sizeof (arr) / sizeof (arr[0]); cout << "Element found at index " << binarySearch(arr, 0, n - 1, x); } // This code is contributed by shivanisinghss2110 |
C
// C program for Binary Search for Rational Numbers // without using floating point arithmetic #include <stdio.h> struct Rational { int p; int q; }; // Utility function to compare two Rational numbers // 'a' and 'b'. It returns // 0 --> When 'a' and 'b' are same // 1 --> When 'a' is greater //-1 --> When 'b' is greater int compare( struct Rational a, struct Rational b) { // If a/b == c/d then a*d = b*c: // method to ignore division if (a.p * b.q == a.q * b.p) return 0; if (a.p * b.q > a.q * b.p) return 1; return -1; } // Returns index of x in arr[l..r] if it is present, else // returns -1. It mainly uses Binary Search. int binarySearch( struct Rational arr[], int l, int r, struct Rational x) { if (r >= l) { int mid = l + (r - l)/2; // If the element is present at the middle itself if (compare(arr[mid], x) == 0) return mid; // If element is smaller than mid, then it can // only be present in left subarray if (compare(arr[mid], x) > 0) return binarySearch(arr, l, mid-1, x); // Else the element can only be present in right // subarray return binarySearch(arr, mid+1, r, x); } return -1; } // Driver method int main() { struct Rational arr[] = {{1, 5}, {2, 3}, {3, 2}, {13, 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)); } |
JAVA
// Java program for Binary Search for Rational Numbers // without using floating point arithmetic class GFG { static class Rational { int p; int q; public Rational( int p, int q) { this .p = p; this .q = q; } }; // Utility function to compare two Rational numbers // 'a' and 'b'. It returns // 0 -. When 'a' and 'b' are same // 1 -. When 'a' is greater //-1 -. When 'b' is greater static int compare(Rational a, Rational b) { // If a/b == c/d then a*d = b*c: // method to ignore division if (a.p * b.q == a.q * b.p) return 0 ; if (a.p * b.q > a.q * b.p) return 1 ; return - 1 ; } // Returns index of x in arr[l..r] if it is present, else // returns -1. It mainly uses Binary Search. static int binarySearch(Rational arr[], int l, int r, Rational x) { if (r >= l) { int mid = l + (r - l)/ 2 ; // If the element is present at the middle itself if (compare(arr[mid], x) == 0 ) return mid; // If element is smaller than mid, then it can // only be present in left subarray if (compare(arr[mid], x) > 0 ) return binarySearch(arr, l, mid - 1 , x); // Else the element can only be present in right // subarray return binarySearch(arr, mid + 1 , r, x); } return - 1 ; } // Driver method public static void main(String[] args) { Rational arr[] = { new Rational( 1 , 5 ), new Rational( 2 , 3 ), new Rational( 3 , 2 ), new Rational( 13 , 2 )}; Rational x = new Rational( 3 , 2 ); int n = arr.length; System.out.printf( "Element found at index %d" , binarySearch(arr, 0 , n - 1 , x)); } } // This code is contributed by Rajput-Ji |
Python3
# Python3 program for Binary Search # for Rational Numbers without # using floating point arithmetic class Rational: def __init__( self , a = 0 , b = 0 ): self .p = a self .q = b # Utility function to compare two # Rational numbers 'a' and 'b'. # It returns # 0 --> When 'a' and 'b' are same # 1 --> When 'a' is greater #-1 --> When 'b' is greater def compare(a: Rational, b: Rational) - > int : # If a/b == c/d then a*d = b*c: # method to ignore division if (a.p * b.q = = a.q * b.p): return 0 if (a.p * b.q > a.q * b.p): return 1 return - 1 # Returns index of x in arr[l..r] if # it is present, else returns -1. It # mainly uses Binary Search. def binarySearch(arr: list , l: int , r: int , x: Rational) - > int : if (r > = l): mid = l + (r - l) / / 2 # If the element is present at the # middle itself if (compare(arr[mid], x) = = 0 ): return mid # If element is smaller than mid, then # it can only be present in left subarray if (compare(arr[mid], x) > 0 ): return binarySearch(arr, l, mid - 1 , x) # Else the element can only be present # in right subarray return binarySearch(arr, mid + 1 , r, x) return - 1 # Driver code if __name__ = = "__main__" : arr = [ Rational( 1 , 5 ), Rational( 2 , 3 ), Rational( 3 , 2 ), Rational( 13 , 2 ) ] x = Rational( 3 , 2 ) n = len (arr) print ( "Element found at index %d" % ( binarySearch(arr, 0 , n - 1 , x))) # This code is contributed by sanjeev2552 |
C#
// C# program for Binary Search for Rational Numbers // without using floating point arithmetic using System; class GFG { class Rational { public int p; public int q; public Rational( int p, int q) { this .p = p; this .q = q; } }; // Utility function to compare two Rational numbers // 'a' and 'b'. It returns // 0 -. When 'a' and 'b' are same // 1 -. When 'a' is greater //-1 -. When 'b' is greater static int compare(Rational a, Rational b) { // If a/b == c/d then a*d = b*c: // method to ignore division if (a.p * b.q == a.q * b.p) return 0; if (a.p * b.q > a.q * b.p) return 1; return -1; } // Returns index of x in arr[l..r] if it is present, else // returns -1. It mainly uses Binary Search. static int binarySearch(Rational []arr, int l, int r, Rational x) { if (r >= l) { int mid = l + (r - l)/2; // If the element is present at the middle itself if (compare(arr[mid], x) == 0) return mid; // If element is smaller than mid, then it can // only be present in left subarray if (compare(arr[mid], x) > 0) return binarySearch(arr, l, mid - 1, x); // Else the element can only be present in right // subarray return binarySearch(arr, mid + 1, r, x); } return -1; } // Driver method public static void Main(String[] args) { Rational []arr = { new Rational(1, 5), new Rational(2, 3), new Rational(3, 2), new Rational(13, 2)}; Rational x = new Rational(3, 2); int n = arr.Length; Console.Write( "Element found at index {0}" , binarySearch(arr, 0, n - 1, x)); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript program for Binary Search for Rational Numbers // without using floating point arithmetic class Rational { constructor(p, q) { this .p = p; this .q = q; } } // Utility function to compare two Rational numbers // 'a' and 'b'. It returns // 0 -. When 'a' and 'b' are same // 1 -. When 'a' is greater //-1 -. When 'b' is greater function compare(a,b) { // If a/b == c/d then a*d = b*c: // method to ignore division if (a.p * b.q == a.q * b.p) return 0; if (a.p * b.q > a.q * b.p) return 1; return -1; } // Returns index of x in arr[l..r] if it is present, else // returns -1. It mainly uses Binary Search. function binarySearch(arr,l,r,x) { if (r >= l) { let mid = l + Math.floor((r - l)/2); // If the element is present at the middle itself if (compare(arr[mid], x) == 0) return mid; // If element is smaller than mid, then it can // only be present in left subarray if (compare(arr[mid], x) > 0) return binarySearch(arr, l, mid - 1, x); // Else the element can only be present in right // subarray return binarySearch(arr, mid + 1, r, x); } return -1; } // Driver method let arr=[ new Rational(1, 5), new Rational(2, 3), new Rational(3, 2), new Rational(13, 2)]; let x = new Rational(3, 2); let n = arr.length; document.write( "Element found at index " , binarySearch(arr, 0, n - 1, x)); // This code is contributed by rag2127 </script> |
输出：
Element found at index 2
时间复杂性： O（对数n）
辅助空间： O（1）
感谢乌特卡什·特里维迪提出上述解决方案。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
