Медиана двух отсортированных массивов с использованием теоремы двоичного поиска - PullRequest
Новая
       27

Медиана двух отсортированных массивов с использованием теоремы двоичного поиска

1 голос
/ 09 июля 2020
• 1000 на основе количества элементов меньше медианы должно быть меньше или равно (n + m + 1) /2.n и быть размером двух массивов соответственно. В случае четного числа элементов среднее берется со следующим элементом. Код выглядит следующим образом. 
  int  n =A.size();
  int  m = B.size();
  if(n < 1){
     if(m%2==0){
        return (B[m/2] + B[m/2-1])/2;
     }else{
        return B[m/2];
     }
 }else if(m < 1){
     if(n%2==0){
        return (A[n/2] + A[n/2-1])/2;
     }else{
        return A[n/2];
     }
 }
int lo = (A[0] < B[0] )? A[0] : B[0];
int hi = (A[n-1] > B[m-1] )? A[n-1] : B[m-1];
while(lo < hi){
    int mid = lo + ( hi - lo+1)/2;
    int t = 0;
    t += upper_bound(A.begin() A.end() mid) - A.begin();
    t += upper_bound(B.begin() B.end() mid) - B.begin();
    if(t > ((n+m+1)/2) ) {
        hi = mid-1;
    }else{
        lo = mid;
    }
    
}
if(  ((n+m)%2))
    return lo;
else{
    int ind1 = upper_bound(A.begin() A.end() lo) - A.begin();
    int ind2 = upper_bound(B.begin() B.end() lo) - B.begin();
    double nxt = ( A[ind1] < B[ind2] )? A[ind1] : B[ind2];
    double x = lo;
    return (x+nxt)/2;
    
}

Код дает неверный результат - это тестовый пример ниже: A = {-50, -41, -40, -19,5,21,28} B = { -50, -21, -10} Запуск dry помог мне понять, где что-то пошло не так, но я не могу понять, в чем заключается логическая ошибка в описанном выше подходе.

1 Ответ

0 голосов
/ 14 июля 2020

В приведенном выше коде есть две логические ошибки:

  1. Мы хотим найти первый элемент, у которого количество равно (n + m + 1) / 2. Но данный код находит первый элемент, где условие ложно. Таким образом, logi обновления c должен быть: 

       if(t < ((n+m+1)/2) ) {
       lo = mid+1;
   }else{
       hi = mid;
   }

    Эта ссылка Двоичный поиск Top Coder имеет хорошее объяснение двух вышеупомянутых сценариев ios.

  2. Когда общее количество элементов четное, для поиска следующего элемента для вычисления среднего необходимо обрабатывать два угловых случая.

    a. Когда у элемента есть повторяющиеся значения. б. Оба ожидаемых элемента присутствуют в одном массиве. 

    if(((n+m)%2))
   return lo;
else{


   int ind1 = lower_bound(A.begin(), A.end(), lo) - A.begin();
   int ind2 = lower_bound(B.begin(), B.end() ,lo) - B.begin();
   double nxt = 0.0;
   //check for duplicates
   if(A[ind1]==lo){
          if(ind2 < B.size())  // check for both elements in same array
               nxt  = ( A[ind1+1] < B[ind2] )? A[ind1+1] : B[ind2];
          else 
               nxt = A[ind1+1];
   }else{
          if(ind1 < A.size())
               nxt = ( A[ind1] < B[ind2+1] )? A[ind1] : B[ind2+1];
          else
               nxt = B[ind2+1];
   }
   double x = lo;
   return (x+nxt)/2;
...