数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会研究
时尚研究
法律研究C程序中不使用浮点运算进行有理数二分查找
在本题中，给定一个有序的有理数数组。我们需要使用二分查找算法，不使用浮点运算在这个有理数数组中查找给定元素。
有理数表示为p / q的形式，其中p和q均为整数。例如，⅔，⅕。
二分查找是通过查找数组的中间值来查找元素的搜索技术。
要从无序的有理数数组中使用二分查找查找元素，其中不允许使用浮点运算。我们将比较分子和分母以找出哪个元素更大或哪个元素是要查找的元素。
示例
让我们为它创建一个程序，
#include <stdio.h>
struct Rational {
int p;
int q;
};
int compare(struct Rational a, struct 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;
}
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, 4}, {2, 3}, {3, 2}, {7, 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));
}输出
Element found at index 2
更新于：22-11-2019
182浏览
广告