検索A [i]を=私は重複

Question

でソートされた配列にと整数のソートされた配列はおそらくを複製考えると、どのようにこれは、のいずれかで問題があるiなA[i]=i

という指標を見つけるのですか私が読んでプログラミングの本（コードのインタビューをクラック）。このソリューションの概要を以下に示します。

public static int magicFast(int[] array, int start, int end) { 

    if (end < start || start < 0 || end >= array.length) { 
    return -1; 
    } 

    int midlndex = (start + end)/2; 
    int midValue = array[midlndex]; 
    if (midValue == midlndex) { 
     return midlndex; 
    } 

    /* Search left */ 
    int leftlndex = Math.min(midlndex - 1, midValue); 
    int left = magicFast(array, start, leftlndex); 
    if (left >= 0) { 
    return left; 
    } 

    /* Search right */ 
    int rightlndex = Math.max(midlndex + i, midValue); 
    int right = magicFast(array, rightlndex, end); 
    return right;  
} 

著者は時間の複雑さについてコメントしていません。しかし、これはO（n）解と思われます。なぜなら、配列要素が異なる問題とは違って、 'mid'点の両側を見る必要があるからです。反復関係はT（n）= 2T（n/2）+ c（中間要素が答えであるかどうかをチェックする一定時間）

これは簡単なリニアスキャンよりもどのように優れていますか？これは、線形時間効率を達成するために過度に複雑に思える。私はここに何かを逃していますか

Answer 1

いいえ、あなたは何も欠けていません。最初のブランチには短絡がありますが、最悪の場合は両方の呼び出しが行われ、その結果、線形時間の再発が発生します。

実際、この問題には、単純なセルプローブの下限によるサブライン時間アルゴリズムはありません。アレイの一部jため

a(i) = i + 1 for i ≠ j 
a(j) = j 

aの家族を考えてみましょう。これらの配列は、固定小数点である特定のエントリを調べることによってのみ区別できます。これは、n - 1プローブの下限を意味します。

元のCTCIの質問で重複が許されないと思われました。変更された配列a(i) - iは非減少で、ゼロ要素のバイナリ検索が可能です。