Поиск медианы двух отсортированных массивов. Можно ли устранить некоторые проверки неравенства?

Question

Работая над этой проблемой и почтовый индекс, мой вопрос заключается в том, безопасно ли изменить эту строку кода

j > 0 and i < m and B[j-1] > A[i] 

в

i < m and B[j-1] > A[i] 

, а также безопасно изменить эту строку кода

i > 0 and j < n and A[i-1] > B[j] 

в

i > 0 and A[i-1] > B[j] 

Я думаю, удалить проверку состояния j безопасен, так как мы уже убедились, что размер A не превышает размер B.

Постановка задачи

Есть два отсортированных массива nums1 и nums2 размера m и n соответственно. Найдите медиану двух отсортированных массивов. Общая сложность времени выполнения должна быть O (log (m + n)).

Реализация

def median(A, B): 
    m, n = len(A), len(B) 
    if m > n: 
     A, B, m, n = B, A, n, m 
    if n == 0: 
     raise ValueError 

    imin, imax, half_len = 0, m, (m + n + 1)/2 
    while imin <= imax: 
     i = (imin + imax)/2 
     j = half_len - i 
     if j > 0 and i < m and B[j-1] > A[i]: 
      # i is too small, must increase it 
      imin = i + 1 
     elif i > 0 and j < n and A[i-1] > B[j]: 
      # i is too big, must decrease it 
      imax = i - 1 
     else: 
      # i is perfect 
      if i == 0: max_of_left = B[j-1] 
      elif j == 0: max_of_left = A[i-1] 
      else: max_of_left = max(A[i-1], B[j-1]) 

      if (m + n) % 2 == 1: 
       return max_of_left 

      if i == m: min_of_right = B[j] 
      elif j == n: min_of_right = A[i] 
      else: min_of_right = min(A[i], B[j]) 

      return (max_of_left + min_of_right)/2.0 

Answer 1

Да, я думаю, вы можете удалить условие j > 0, потому что

j = half_len - i 

и вы уже проверить, что i<m и (m + n + 1)/2 должно быть больше, чем m так n>=m

такой же f или второе условие j < n. Вы уже убедитесь, что i>0, что гарантирует, что j может быть не более (2n+1)/2 - 1, который меньше n и, следовательно, автоматически удовлетворяет вашему состоянию