自身の要素に重複が無い昇順の配列同士で、共通している要素を求めたい


C言語についての質問です。  
二つの配列A,Bがありそれぞれに整数が格納されていて、配列の中の数は昇順にソートされていて、配列Aの中には重複する数がなく、それは配列Bについても一緒である。  
ただし、配列AとBのサイズは同じとは限らない。

それを踏まえて配列AとBの中には重複する数があり、その重複して含まれる数を出力するプログラムを教えてください




### 無駄のある方法

まず、愚直に解くのであれば、配列 a の要素が配列 b に含まれるかどうか1つずつ調べれば良いです。たとえば以下の例で考えてみます。

[code]

    int a[] = {1, 5, 9};
    int b[] = {2, 3, 5, 7, 11};
    
[/code]

この例であれば、まず `a[0]` である `1` が `b` に含まれるか調べます。含まれません。そのあと `a[1]` である `5`
が含まれるか調べます。含まれます。最後に `a[2]` である `9` が含まれるか調べます。含まれません。含まれた回数を数えれば、`a` と `b`
が重複して含んでいる要素の数が分かります。

しかしこの方法には無駄があります。この方法は `a` の要素 1 つごとに `b` の要素をイチから探索しますが、2
つの配列がソートされているという仮定を使うともっと効率よく調べることができるのです。

### より効率的な方法

2 つの配列は共にソートされているので、2 つの配列を最初の要素から同時に調べることができます。具体的には次のようなアルゴリズムです。

[code]

    1. count = 0 と初期化する
    2. i = 0, j = 0 と初期化する
    3. a[i] か b[j] のどちらかが配列末尾を通り越すまで以下を繰り返す:
        // 見ている場所が等しければ、count を 1 増やして次にいく
        2-1. もし a[i] == b[j] なら:
            2-1-1. count++
            2-1-2. i++, j++  // それぞれの配列の中では要素が重複していないのでこれで良い
        // どちらかが真に小さければ、小さい方だけ次に進める
        2-2. そうでなくて、もし a[i] < b[j] なら:
            2-2-1. i++
        2-3. そうでないなら (つまり a[i] > b[j] なら):
            2-3-1. j++
    4. count を出力する
    
[/code]

このアルゴリズムは配列の要素の小さい方から順番に比較しています。`i` と `j`
がそれぞれの配列を「見ている場所」であり、見ている場所を徐々に後ろに動かしています。2
つの配列はソートされているので、既に通り越した要素は今見ている場所の要素とは絶対に等しくないというのがキーポイントです。

先ほどと同じ例で、このアルゴリズムの動作を確かめてみます。

[code]

    int a[] = {1, 5, 9};
    int b[] = {2, 3, 5, 7, 11};
    
[/code]

[code]

     i | j | a[i] | b[j] |
    ----------------------------------------------
     0 | 0 |    1 |    2 | a[i] の方が小さいので i++
     1 | 0 |    5 |    2 | b[j] の方が小さいので j++
     1 | 1 |    5 |    3 | b[j] の方が小さいので j++
     1 | 2 |    5 |    5 | a[i] == b[j]！
     2 | 3 |    9 |    7 | b[j] の方が小さいので j++
     2 | 4 |    9 |   11 | a[i] の方が小さいので i++ → a の終端に達したので終了
    
[/code]

このアルゴリズムを実際に実装したものは [Wandbox
に置いておきます](https://wandbox.org/permlink/n1FkcG5a4eyQbQX1)。

