資料結構
網路
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瀏覽
廣告