C++毎日1題(2つの秩序ある配列の中位数を見つける)

タイトル:Median of Two Sorted Arrays There are two sorted arrays A and B 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))
分析:
1.log(m+n)を見るとすぐに分治法を思いつく
ここでは2つの秩序ある配列なので、2つの秩序ある配列は固定された奇数の数になります.つまり、仮想に「#」を加えることです.仮想加算で便利です.したがって、2つの配列の合計は2 m+2 n+2であり、1つ目がm個で、2つ目がn個であると仮定すると、このような2つの秩序配列が合併した後の中位数がm+n+1であると仮定すると、なぜこのように加算されるのでしょうか.このように加算した後、各位置は/2によって元の要素の位置を得ることができるからである.   
2 .さらにまとめます.
配列を奇数に一定にして、2つの配列の長さを必ず奇数または偶数に加算する方法はありませんか?
実際には,‘#’(このtrickはmanacherアルゴリズムにも応用されている)を仮想的に加え,配列長を奇数(2 n+1を奇数)に一定にする.Ps.仮想加算であることに注意してください.実はこのステップはありません.次の変換によって、仮想加算後の各要素が元の要素と一つ一つ対応することを保証することができます.
前len後len[14 7 9]4[#1#4#7#9#]9[23 5]3[#2#3#5#]7マッピング関係は何のメリットがあるのか、なぜこのように加算されるのか.このように加算した後、各位置は/2によって元の要素の位置を得ることができるからである.
原位置新位置除2后0 1 0 1 5 2仮想配列で「割」を表すだけでなく、割が容易で、「#」に切ると2要素の间に割ることになり、数字に切ると2つの部分に切りつけることになります.
奇妙なことに、どんな状況でも
Li = (Ci-1)/2  Ri = Ci/2
例:1.4/7の間で‘#’,C=4,L=(4-1)/2=1,R=4/2=2はちょうど4と7の元の位置です!  2. 3に割り、C=3、L=(3-1)/2=1、R=3/2=1、ちょうど3の位置!
残りのことはやりやすくて、2つの配列を1つの仮想的な配列Aと見なして、現在2 m+2 n+2の要素があって、m+n+1のところに切って、だから私達はm+n+1の位置の要素とm+n+2の位置の要素を見つけるだけでいいです.左:A[m+n+1]=Max(L 1+L 2)右:A[m+n+2]=Min(R 1+R 2)
Mid = (A[m+n+1]+A[m+n+2])/2         = (Max(L1+L2) + Min(R1+R2) )/2
2つの配列の中で切る案を探すのは、上の案です.
分治の考え方に上の知識があった後、今の問題はどのように分治の思想を利用するかです.
どうやって分けますか.一番速い分の案は二分で、2つの配列がありますが、私たちはどれに対して二分しますか?これまでの解析から,C 1またはC 2が確定すれば,もう1つも確定することが分かった.ここで,効率のために,C 1と仮定すると,長さが短いものを2点に選んだに違いない.
 
 
L1
R1
L2
R2
どうやって治すの?比較も簡単で,L 1,L 2,R 1,R 2を比較することを前に解析した.-L 1>R 2、C 1を小さくし、C 2を大きくします.—>C 1を左に二分-L 2>R 1、C 1を大きくし、C 2を小さくします.—>C 1右二分
国境を越えた問題C 1やC 2が行き詰まったらどうしますか?この場合、配列が完全に中値以下またはそれ以上の場合に発生します.-C 1=0-配列1全体が中値より大きく、L 1=nums 1(((c 1-1)/2)-C 2=0-配列1全体が中値より小さく、L 2-nums 2((c 2-1)/2)
-C 1=2*n-----配列1全体が中値より小さく、R 1=nums 1(c 1/2)
-C 2=2*n-----配列2は全体的に中値より小さく、R 2=nums 2(c 2/2);
テストコード:

#include 
#include 
#include 
#include 
using namespace  std;

/*
 *             
*/
class leet_04{
public:

double findMediaSortedArray(const vector& nums1,const vector&nums2)
{
    int n=nums1.size();
    int m=nums2.size();
    if(n>m)//             。  
        return findMediaSortedArray(nums2,nums1);
    int L1,L2,R1,R2,c1,c2,left=0,right=2*n;//     #    2n+1,             
    while(left<=right) //     
    {
      c1=(left+right)/2;//c1       
      c2=m+n-c1;//k=n+m.           k
      L1=(c1==0)?INT_MIN:nums1[(c1-1)/2];
      R1=(c1==2*n)?INT_MAX:nums1[c1/2];
      L2=(c2==0)?INT_MIN:nums2[(c2-1)/2];
      R2=(c2==2*m)?INT_MAX:nums2[(c2/2)];
      if(L1>R2)
          right=c1-1;
      else if(L2>R1)
          left=c1+1;
      else
          break;
    }
    return ((max(L1,L2)+min(R1,R2))/2.0);
 }
};
//test
int main()
{
  int arr1[]={1,2};
  int arr2[]={3,4};
  vector nums1(arr1,arr1+sizeof(arr1)/sizeof(int));
  vector nums2(arr2,arr2+sizeof(arr2)/sizeof(int));
  leet_04 test;
  double mediaval=test.findMediaSortedArray(nums1,nums2);
  cout<