Un racional se representa como p/qb, por ejemplo 2/3. Dada una array ordenada de números racionales, cómo buscar un elemento mediante la búsqueda binaria. No se permite el uso de aritmética de punto flotante.
Ejemplo:
Input: arr[] = {1/5, 2/3, 3/2, 13/2}
x = 3/2
Output: Found at index 2
Le recomendamos encarecidamente que minimice su navegador y que pruebe esto usted mismo primero.
Para comparar dos números racionales p/q y r/s, podemos comparar p*s con 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>
Producción:
Element found at index 2
Complejidad de tiempo: O (log n)
Espacio Auxiliar: O(1), ya que no se ha ocupado ningún espacio extra.
Gracias a Utkarsh Trivedi por sugerir la solución anterior.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA