2つのソートされた配列で見つからない番号を見つける

Question

インタビューの質問があります。

2つのソート配列が指定されています。
最初はどちらも要素のセットが設定されていますが、1つの要素が1つの配列から削除されています。
削除された要素を検索します。
制約は、私たちが元の場合はO（LOGN） でインプレース、それをやっに持っている：それは擬似コードであるので、

arr1[]={1,2,3,8,12,16}; 
arr2[]={1,2,8,12,16}; 

削除要素は、私は携帯から入力しています3

Answer 1

ですが、必要になります取得：

take arr1.len/2.それは3. arr1 [3]とarr2 [3]を確認します。彼らが等しい場合、失われたvsalueは3以上のインデックスにあります。それ以外では3未満です。ここでは8と12が得られます。インデックス3/2 = 1をとる。 arr1 [1]とarr2 [1]を比較してください。それらは等しいので、欠落はインデックス1の後で3の前です。したがって、arr1 [2] = 3です。

これは考えです。あなたはバイナリ検索をしており、毎回検索エリアを半分にしています。あなたは、比較することによって配列の左または右の部分を取る。あなたはこれを実装していくつかの点検をするだけですが、私の考えは明らかです。