Search in an Array of Rational Numbers without floating point arithmetic

Given a sorted array of rational numbers, where each rational number is represented in the form p/q (where p is the numerator and q is the denominator), the task is to find the index of a given rational number x in the array. If the number does not exist in the array, return -1.

Examples:  

Input: arr[] = [1/5, 2/3, 3/2, 13/2], x = 3/2
Output: 2
Explanation: The given rational element is present at index 2.

Input: arr[] = [1/5, 2/3, 3/2, 13/2], x = 5/1
Output: -1
Explanation: The given rational number 5/1 does not exist in the array.

Input: arr[] = [1/2, 2/3, 3/4, 4/5], x = 1/2
Output: 0
Explanation: The given rational number 1/2 is present at index 0 in the array.

Approach:

The idea is to use binary search to efficiently find the index of the given rational number x in the sorted array of rational numbers. Since the array is sorted, we can compare rational numbers without using floating-point arithmetic by cross-multiplying the numerators and denominators, allowing us to determine whether to search in the left or right half of the array.

Step by step approach:

1. Initialize two pointers, left and right, to represent the start and end of the search range in the array.
2. Calculate the middle index of the current search range using mid = left + (right - left) / 2.
3. Compare the middle element with x using cross-multiplication:
   • If arr[mid] == x, return mid (index found).
   • If arr[mid] > x, update right = mid - 1 to search in the left half.
   • If arr[mid] < x, update left = mid + 1 to search in the right half.
4. Repeat steps 2-3 until left exceeds right.
5. If the loop ends without finding x, return -1 (element not found).

// C++ program for Binary Search for // Rational Numbers without using // floating-point arithmetic #include <iostream> #include <vector> using namespace std; class Rational{ public: int p; int q;  Rational(int num, int den) {  p = num;  q = den; } }; // Utility function to compare two // Rational numbers 'a' and 'b'. // It returns: // 0 --> When 'a' and 'b' are equal // 1 --> When 'a' is greater than 'b' // -1 --> When 'b' is greater than 'a' int compare(Rational& a, Rational& b) {   // If a/b (operator) b/a, then  // a.p * b.q (op) a.q * b.p 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 the index of 'x' in the vector 'arr' within the range [l, r] // if it is present, else returns -1. // It uses Binary Search for efficient searching. int binarySearch(vector<Rational>& arr, Rational& x) {  int l = 0, r = arr.size()-1;    while (l <= r) {  int mid = l + (r - l) / 2;  // If the element is present at the middle itself  if (compare(arr[mid], x) == 0)  return mid;  // If the element is smaller than the middle element,  // it can only be present in the left subarray  if (compare(arr[mid], x) > 0)  r = mid - 1;  // Else, the element can only be   // present in the right subarray  else  l = mid + 1;  }  // Element is not present in the array  return -1; } int main() { vector<Rational> arr = { {1, 5}, {2, 3}, {3, 2}, {13, 2} }; Rational x(3, 2); cout << binarySearch(arr, x); return 0; } 

// Java program for Binary Search for // Rational Numbers without using // floating-point arithmetic class Rational { int p; int q; Rational(int num, int den) { p = num; q = den; } } class GfG {   // Utility function to compare two  // Rational numbers 'a' and 'b'.  // It returns:  // 0 --> When 'a' and 'b' are equal  // 1 --> When 'a' is greater than 'b'  // -1 --> When 'b' is greater than 'a' static int compare(Rational a, 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; }  // Returns the index of 'x' in the array 'arr' within the range [l, r]  // if it is present, else returns -1.  // It uses Binary Search for efficient searching. static int binarySearch(Rational[] arr, Rational x) { int l = 0, r = arr.length - 1; while (l <= r) { int mid = l + (r - l) / 2; // If the element is present at the middle itself if (compare(arr[mid], x) == 0) return mid; // If the element is smaller than the middle element, // it can only be present in the left subarray if (compare(arr[mid], x) > 0) r = mid - 1; // Else, the element can only be // present in the right subarray else l = mid + 1; } // Element is not present in the array return -1; } 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); System.out.println(binarySearch(arr, x)); } } 

# Python program for Binary Search for # Rational Numbers without using # floating-point arithmetic class Rational: def __init__(self, num, den): self.p = num self.q = den # Utility function to compare two # Rational numbers 'a' and 'b'. # It returns: # 0 --> When 'a' and 'b' are equal # 1 --> When 'a' is greater than 'b' # -1 --> When 'b' is greater than 'a' def compare(a, 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 # Returns the index of 'x' in the list 'arr' within the range [l, r] # if it is present, else returns -1. # It uses Binary Search for efficient searching. def binarySearch(arr, x): l, r = 0, len(arr) - 1 while l <= r: mid = l + (r - l) // 2 # If the element is present at the middle itself if compare(arr[mid], x) == 0: return mid # If the element is smaller than the middle element, # it can only be present in the left subarray if compare(arr[mid], x) > 0: r = mid - 1 # Else, the element can only be  # present in the right subarray else: l = mid + 1 # Element is not present in the array return -1 if __name__ == "__main__": arr = [Rational(1, 5), Rational(2, 3), Rational(3, 2), Rational(13, 2)] x = Rational(3, 2) print(binarySearch(arr, x)) 

// C# program for Binary Search for // Rational Numbers without using // floating-point arithmetic using System; class Rational {  public int p;  public int q;     public Rational(int num, int den) {  p = num;  q = den;  } } class GfG {    // Utility function to compare two  // Rational numbers 'a' and 'b'.  // It returns:  // 0 --> When 'a' and 'b' are equal  // 1 --> When 'a' is greater than 'b'  // -1 --> When 'b' is greater than 'a'  static int compare(Rational a, 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;  }    // Returns the index of 'x' in the array 'arr' within the range [l, r]  // if it is present, else returns -1.  // It uses Binary Search for efficient searching.  static int binarySearch(Rational[] arr, Rational x) {  int l = 0, r = arr.Length - 1;    while (l <= r) {  int mid = l + (r - l) / 2;    // If the element is present at the middle itself  if (compare(arr[mid], x) == 0)  return mid;    // If the element is smaller than the middle element,  // it can only be present in the left subarray  if (compare(arr[mid], x) > 0)  r = mid - 1;    // Else, the element can only be   // present in the right subarray  else  l = mid + 1;  }    // Element is not present in the array  return -1;  }    static void Main() {  Rational[] arr = { new Rational(1, 5),   new Rational(2, 3), new Rational(3, 2),  new Rational(13, 2) };  Rational x = new Rational(3, 2);  Console.WriteLine(binarySearch(arr, x));  } } 

// JavaScript program for Binary Search for // Rational Numbers without using // floating-point arithmetic class Rational {  constructor(num, den) {  this.p = num;  this.q = den;  } } // Utility function to compare two // Rational numbers 'a' and 'b'. // It returns: // 0 --> When 'a' and 'b' are equal // 1 --> When 'a' is greater than 'b' // -1 --> When 'b' is greater than 'a' function compare(a, 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; } // Returns the index of 'x' in the array 'arr' within the range [l, r] // if it is present, else returns -1. // It uses Binary Search for efficient searching. function binarySearch(arr, x) {  let l = 0, r = arr.length - 1;    while (l <= r) {  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 the element is smaller than the middle element,  // it can only be present in the left subarray  if (compare(arr[mid], x) > 0)  r = mid - 1;  // Else, the element can only be   // present in the right subarray  else  l = mid + 1;  }  // Element is not present in the array  return -1; } let arr = [new Rational(1, 5), new Rational(2, 3), new Rational(3, 2), new Rational(13, 2)]; let x = new Rational(3, 2); console.log(binarySearch(arr, x)); 

2

Time Complexity: O(log n)
Auxiliary Space: O(1),  since no extra space has been taken.