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)).
给两个有序表，O(log (m+n)).求中位数，其实就是求第k小的数
首先假设数组A和B的元素个数都大于k/2，我们通过比较A[k/2-1]和B[k/2-1]两个元素，不论结果如何，都可以确定有k/2的元素被确定是在第k小以内的(假设是A的元素<B的元素)，然后我们接下来比较A的剩余部分和B即可。
每次比较都可以砍掉K/2的元素（K在变化）
因此是log(k)次比较.
k可以取到n+m
因此复杂度是O（n+m）
#include <bits/stdc++.h> #include <iostream> using namespace std; typedef long long ll; double solve(vector<int>& nums1,int sa,int n, vector<int>& nums2,int sb,int m,int k) { if (n>m) return solve(nums2,sb,m,nums1,sa,n,k); if (n==0) return nums2[sb+k-1]; if (k==1) return min(nums1[sa],nums2[sb]); int pa=min(n,k/2),pb=k-pa; if (nums1[sa+pa-1]<nums2[sb+pb-1]) return solve(nums1,sa+pa,n-pa,nums2,sb,m,k-pa); else return solve(nums1,sa,n,nums2,sb+pb,m-pb,k-pb); } double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { int n=nums1.size(),m=nums2.size(); if ((n+m)&1) return solve(nums1,0,n,nums2,0,m,(m+n+1)/2); else return (solve(nums1,0,n,nums2,0,m,(m+n)/2)+ solve(nums1,0,n,nums2,0,m,(m+n)/2+1))/2; } vector<int >a,b; int main() { int n,m,x; cin>>n>>m; for(int i=1; i<=n; i++)scanf("%d",&x),a.push_back(x); for(int i=1; i<=m; i++)scanf("%d",&x),b.push_back(x); double ans=findMedianSortedArrays(a,b); cout<<ans<<endl; return 0; }
