ในปัญหานี้ เราได้รับอาร์เรย์ที่จัดเรียงของจำนวนตรรกยะ และเราต้องค้นหาองค์ประกอบที่กำหนดโดยใช้อัลกอริทึมการค้นหาแบบไบนารีสำหรับอาร์เรย์จำนวนตรรกยะนี้โดยไม่ต้องใช้เลขทศนิยม
จำนวนตรรกยะ คือตัวเลขที่แสดงในรูปแบบ 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
