Trong bài toán này, chúng ta đưa ra một mảng các số hữu tỉ đã được sắp xếp. và chúng ta phải tìm kiếm phần tử đã cho bằng thuật toán tìm kiếm nhị phân cho mảng số hữu tỉ này mà không sử dụng số học dấu phẩy động.
A Số hợp lý là số được biểu diễn dưới dạng p / q trong đó cả p và q đều là số nguyên. Ví dụ:⅔, ⅕.
Tìm kiếm nhị phân là kỹ thuật tìm kiếm hoạt động bằng cách tìm giữa mảng để tìm phần tử.
để tìm phần tử bằng cách sử dụng tìm kiếm nhị phân từ một mảng các số hữu tỉ đã được sắp xếp, trong đó số học dấu phẩy động không được phép. Chúng tôi sẽ so sánh tử số và mẫu số để tìm phần tử nào Lớn hơn hoặc phần tử nào là phần tử cần tìm.
Ví dụ
Hãy tạo một chương trình cho việc này,
#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));
} Đầu ra
Element found at index 2