부동 소수점 연산 없이 C 언어로 유리수 배열 이진 탐색 구현하기

이 문제에서는 정렬된 유리수 배열이 주어지며, 부동 소수점 산술을 사용하지 않고 이진 탐색(Binary Search) 알고리즘을 이용해 주어진 원소를 찾아야 합니다.

유리수(Rational Number)란 p/q 형태로 표현되는 수를 말하며, 이때 p와 q는 모두 정수입니다. 예를 들어 ⅔, ⅕가 대표적인 유리수입니다.

이진 탐색은 배열의 중간 위치를 기준으로 탐색 범위를 절반씩 줄여가며 원소를 찾는 효율적인 탐색 기법입니다.

접근 방법

부동 소수점 연산이 허용되지 않는 상황에서 정렬된 유리수 배열을 이진 탐색하려면, 분자와 분모를 활용한 교차 곱셈(cross multiplication)으로 두 유리수의 대소 관계를 비교하면 됩니다.

두 유리수 a/b와 c/d를 비교할 때 실제 나눗셈을 수행하는 대신 a×d와 b×c의 크기를 비교합니다. 이 방법은 정수 연산만으로 두 유리수의 크기를 정확히 판단할 수 있으며, 부동 소수점 연산에서 발생할 수 있는 오차를 완전히 제거할 수 있다는 장점이 있습니다.

비교 로직

• a.p × b.q == a.q × b.p → 두 유리수가 같음 (0 반환)
• a.p × b.q > a.q × b.p → 첫 번째 유리수가 더 큼 (1 반환)
• 그 외의 경우 → 첫 번째 유리수가 더 작음 (-1 반환)

이 비교 함수를 이진 탐색에 적용하면 시간 복잡도 O(log n)으로 목표 원소를 빠르게 찾을 수 있습니다.

예제 코드

#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

위 예제에서 배열 {1/4, 2/3, 3/2, 7/2}에서 3/2를 검색하면 해당 원소가 인덱스 2에 위치하고 있음을 확인할 수 있습니다.