2つの配列に同じ数字があるかどうかを判断する

2つの配列に同じ数字があるかどうかを判断する
2つの並べ替えられた配列を与えて、どのように効率的にこの2つの配列に同じ数字があるかを判断しますか?この問題はまずO(nlogn)のアルゴリズムを考えた.任意に1つの配列を選択して、この配列のすべての要素を遍歴して、遍歴の過程の中で、別の配列の中で第1の配列の中の各要素に対してbinary searchを行います.C++で実現するコードは以下の通りである.

bool findcommon(int a[],int size1,int b[],int size2)
{
     int i;
     for(i=0;i<size1;i++)
     {
          int start=0,end=size2-1,mid;
          while(start<=end)
          {
               mid=(start+end)/2;
               if(a[i]==b[mid])
                    return true;
               else if (a[i]<b[mid])
                    end=mid-1;
               else
                    start=mid+1;
          }
     }
     return false;
}

後にO(n)アルゴリズムが発見された.両方の配列が順番に並んでいるからです.だから一度だけ遍歴すればいいのです.まず2つの下付き文字を設定し,それぞれ2つの配列の開始アドレスに初期化し,順次前進する.推進のルールは、2つの配列の中の数字を比較し、小さい配列の下付き文字を一歩前進させ、いずれの配列の下付き文字が配列の末尾に達するまで、同じ数字に出会っていない場合は、配列に同じ数字がないことを示します.

bool findcommon2(int a[], int size1, int b[], int size2)
{
     int i=0,j=0;
     while(i<size1 && j<size2)
     {
          if(a[i]==b[j])
               return true;
          if(a[i]>b[j])
               j++;
          if(a[i]<b[j])
               i++;
     }
     return false;
}