There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

一開始寫的可惜出錯(cuò)，邊界情況判斷不清，這并不是一個(gè)簡單的問題。

先來一個(gè)比較無腦的ruby黑魔法

def find_median_sorted_arrays(a, b)
  c = (a + b).sort
  mid = c.size/2
  ( c.size.odd?) ? c[mid] : ((c[mid]+c[mid-1]).to_f/2)
end

下面是分治法，速度會(huì)快一點(diǎn)

def find_median_sorted_arrays(a,b)
  len=a.size+b.size
  return find_kth(a,b,len/2+1) if len.odd? 
  (find_kth(a,b,len/2)+find_kth(a,b,len/2+1))*0.5
end
## k>0
def find_kth(a,b,k)   
  return find_kth(b,a,k) if a.size<b.size  #ensure a.size >= b.size
  return a[k-1] if b.size==0
  return a[0]>b[0] ? b[0] : a[0] if k==1
  lenb=[b.size,k/2].min
  lena=k-lenb
  return find_kth(a[lena..-1],b,k-lena) if a[lena-1]<b[lenb-1]
  find_kth(a,b[lenb..-1],k-lenb)
end

臨界情況