c++ - C++中两个大小相等的排序数组中位数的实现

Question

我试图在 C++ 中实现上述算法，但在计算数组的一半长度时不知何故出现舍入错误。

尝试:

#include <iostream>
#include <math.h>
using namespace std;

void print_array(int arr[], int size){
    for(int i = 0; i < size; i++){
        cout << arr[i] << "-";
    }
    cout << endl;
}

float median_h(int arr[], int size){
  float median = 0.0;
  if(size%2 == 0)
    median = (arr[size/2] + arr[(size/2)-1])/2;
  else median = arr[(int)ceil(size/2)];
  return median;
}

float median(int arr1[], int arr2[], int size_1, int size_2){
   cout << size_1 << endl;
   print_array(arr1,size_1);
   cout << size_2 << endl;
   print_array(arr2,size_2);
   cout << endl;
   float m1 = median_h(arr1,size_1);
   float m2 = median_h(arr2,size_2);
   float median_res = 0.0;
   if(size_1 == 1)
      median_res = (arr1[0] + arr2[0])/2;
   else if(m1 == m2)
      median_res = m1;
   else{
     int index = 0;
     int size = ceil(size_1/2);
     (size_1 % 2 == 0)? index = size_1/2 : index = floor(size_1/2); 
     if(m1 < m2)
       median_res = median(arr1 + index,arr2, size, size);    
     else
       median_res = median(arr1,arr2 + index, size, size);
   }
   return median_res;
}



int main(void){
    int arr1[] = {1,12,15,26,38};
    int arr2[] = {2,13,17,30,45};

    float med = median(arr1,arr2,5,5);
    cout << med << endl;

}

这是输出:

  output:

    5
    1-12-15-26-38-
    5
    2-13-17-30-45-

    2
    15-26-
    2
    2-13-

    1
    15-
    1
    13-

    14

我期望在第二次递归迭代中长度为 3，但我得到的是 2。我不知道 ceil(5/2) 有什么问题。应该是 3。

Answer 1

 int size = ceil(size_1/2);

由于 size_1 是 int 类型，因此将其除以 2 隐式等同于取除法的底数。例如如果 size_1 等于 3，则 (size_1/2) 将返回 1，而不是 1.5。

因此，ceil() 不会在这里为您提供您想要的东西，因为传递给它的值已经下降。

你也可以这样做:

int size = ceil(size_1/2.0f);  // now we're dividing by a float, so the result will be non-integer

...但是您可以得到相同的结果，而不必求助于 float 学，只需在除法之前将值加 1 即可:

int size = (size_1+1)/2;