Рубрики

Бинарный поиск рациональных чисел без использования арифметики с плавающей запятой

Рациональное представляется как p / qb, например 2/3. Учитывая отсортированный массив рациональных чисел, как искать элемент с помощью бинарного поиска. Использование арифметики с плавающей точкой не допускается.

Пример:

Input:  arr[] = {1/5, 2/3, 3/2, 13/2}
        x = 3/2
Output: Found at index 2

Мы настоятельно рекомендуем вам свернуть браузер и попробовать это в первую очередь.

Чтобы сравнить два рациональных числа p / q и r / s, мы можем сравнить p * s с q * r.

C ++

// C программа для двоичного поиска рациональных чисел
// без использования арифметики с плавающей точкой
#include <stdio.h>

  

struct Rational

{

    int p;

    int q;

};

  
// Сервисная функция для сравнения двух рациональных чисел
// 'a' и 'b'. Возвращается
// 0 -> Когда 'a' и 'b' совпадают
// 1 -> Когда «а» больше
// - 1 -> Когда 'b' является отличным

int compare(struct Rational a, struct Rational b)

{

    // Если a / b == c / d, то a * d = b * c:

    // метод игнорирования деления

    if (a.p * b.q == a.q * b.p)

        return 0;

    if (a.p * b.q > a.q * b.p)

        return 1;

    return -1;

}

  
// Возвращает индекс x в arr [l..r], если он присутствует, иначе
// возвращает -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, 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-программа для двоичного поиска рациональных чисел
// без использования арифметики с плавающей точкой

class GFG

{

  

static class Rational

{

    int p;

    int q;

  

    public Rational(int p, int q)

    {

        this.p = p;

        this.q = q;

    }

      
};

  
// Сервисная функция для сравнения двух рациональных чисел
// 'a' и 'b'. Возвращается
// 0 -. Когда «а» и «б» совпадают
// 1 -. Когда «а» больше
// - 1 -. Когда «б» лучше

static int compare(Rational a, Rational b)

{

    // Если a / b == c / d, то a * d = b * c:

    // метод игнорирования деления

    if (a.p * b.q == a.q * b.p)

        return 0;

    if (a.p * b.q > a.q * b.p)

        return 1;

    return -1;

}

  
// Возвращает индекс x в arr [l..r], если он присутствует, иначе
// возвращает -1. Он в основном использует бинарный поиск.

static int binarySearch(Rational arr[], int l, int r,

                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;

}

  
// Метод драйвера

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

}
}

  
// Этот код предоставлен Rajput-Ji

C #

// C # программа для двоичного поиска рациональных чисел
// без использования арифметики с плавающей точкой

using System;

  

class GFG

{

  

class Rational

{

    public int p;

    public int q;

  

    public Rational(int p, int q)

    {

        this.p = p;

        this.q = q;

    }

      
};

  
// Сервисная функция для сравнения двух рациональных чисел
// 'a' и 'b'. Возвращается
// 0 -. Когда «а» и «б» совпадают
// 1 -. Когда «а» больше
// - 1 -. Когда «б» лучше

static int compare(Rational a, Rational b)

{

    // Если a / b == c / d, то a * d = b * c:

    // метод игнорирования деления

    if (a.p * b.q == a.q * b.p)

        return 0;

    if (a.p * b.q > a.q * b.p)

        return 1;

    return -1;

}

  
// Возвращает индекс x в arr [l..r], если он присутствует, иначе
// возвращает -1. Он в основном использует бинарный поиск.

static int binarySearch(Rational []arr, int l, int r,

                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;

}

  
// Метод драйвера

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

}
}

  
// Этот код предоставлен 29AjayKumar

Выход:

Element found at index 2

Спасибо Уткаршу Триведи за предложенное решение.

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Бинарный поиск рациональных чисел без использования арифметики с плавающей запятой

0.00 (0%) 0 votes