A rational is represented as p/qb, for example 2/3. Given a sorted array of rational numbers, how to search an element using Binary Search. Use of floating-point arithmetic is not allowed.
Example:
Input: arr[] = {1/5, 2/3, 3/2, 13/2}
x = 3/2
Output: Found at index 2
We strongly recommend you to minimize your browser and try this yourself first.
To compare two rational numbers p/q and r/s, we can compare p*s with 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 greaterint 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 codeint 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 greaterint 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 methodint 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 arithmeticclass 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 greaterstatic 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 methodpublic 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 arithmeticclass 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 greaterdef 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 codeif __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 arithmeticusing 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 greaterstatic 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 methodpublic 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 arithmeticclass 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 greaterfunction 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 methodlet 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> |
Output:
Element found at index 2
Time Complexity: O(log n)
Auxiliary Space: O(1), since no extra space has been taken.
Thanks to Utkarsh Trivedi for suggesting above solution.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
