c++ - 需要帮助为我的算法中的缺陷提出优雅的修复

Question

我正在为一家大型在线零售商的面试而练习，现在我正在尝试为“两个已排序数组的中位数”问题提出一个优雅的解决方案。我知道 youtube 上提出的解决方案，但我正在尝试编写另一种方法。我写出来了

include <stdio.h>

int M2SA ( int * A, int m, int * B, int n )
{
   /* Returns the median of two sorted arrays A and B of lengths m and n respectively. 
      Assumes A and B aren't both empty. 
   */ 
   int ida = 0, idb = 0, idmed = (m+n)/2;
   while ((ida + idb) != idmed)
   {
     if (A[ida] < B[idb])
        ++ida;
     else
        ++idb;
   }
   return (A[ida] < A[idb] ? A[ida] : B[idb]);
} 



int main()
{
    int arr1 [] = {1, 1, 59, 69};
    int arr2 [] = {-4, 0, 49, 59, 59, 59};
    printf("%d", M2SA(arr1, sizeof(arr1)/sizeof(int), arr2, sizeof(arr2)/sizeof(int)));
    return 0;
}

它打印出正确答案 (59)，但我意识到我的算法存在一个缺陷，即只有当 idmed 不大于 m< 时我的算法才有效 或 n。例如，如果数组是 {1} 和 {69, 293, 393, 1923129}，则 ida 等于 1 在 while 循环的第一次迭代之后，因此 while 循环的第二次迭代尝试访问 A[1]。但是，我想不出一个简单的修复方法来添加到我的代码中。有没有简单的？

Answer 1

这是对您的解决方案的优雅修复:

int ida = 0, idb = 0, idmed = (m + n) / 2;
while (ida < m && idb < n && ida + idb < idmed) {
    A[ida] < B[idb] ? ++ida : ++idb;
}
if (ida == m) return B[idmed - m];
if (idb == n) return A[idmed - n];
return A[ida] < B[idb] ? A[ida] : B[idb];