特定の要素のソートされた配列の範囲のインデックスを見つける

Question

私は、配列がソートされている配列で作業しています。タスクは、値の範囲を見つけることです。

私たちは、このソートされた配列があるとしましょう：私たちは、私たちはすぐに要素1の最初のインデックスがあることを発見素子1のためのレンジ・最小値と最大値を見つける必要があり 例

int[] array = {1,1,1,3,3,9,10} 

を0であり、範囲maxは2である。

ここで、0と2の間の範囲はすべて1であることがわかっている。検索された要素が3の場合、その範囲は3-4であり、要素9では範囲6-6である。

これを行うには線形検索を使用しましたが、これを行うより高速な方法があると聞きましたか？

Answer 1

あなたは、左端と右端の位置を見つけるためにバイナリ検索の2つのバージョンを使用することができます。

int[] array = { 1, 1, 1, 3, 3, 9, 10 } 
int value = ... 

int leftmost(int min, int max) 
{ 
    if (min == max) return min 
    int mid = (min + max)/2 

    if (array[mid] < value) return leftmost(mid + 1, max) 
    else return leftmost(min, mid) 
} 

int rightmost(int min, int max) 
{ 
    if (min == max) return min 
    int mid = (min + max + 1)/2 

    if (array[mid] > value) return rightmost(min, mid - 1) 
    else return rightmost(mid, max) 
} 

ちょうどmin=0とmax=array.length-1で電話をかけること。時間の複雑さはO(logn)です。

あなたはこの（0-basedインデックス）のような出力が得られます：

value=1 -> left=0, right=2 
value=3 -> left=3, right=4 
value=9 -> left=5, right=5 
value=10 -> left=6, right=6 

Answer 2

バイナリ検索がはるかに高速になります。あなたはこれについていくつかの洞察を得ることができますhere

Answer 3

より大きい配列がバイナリで、次に線形であると仮定します。

アレイのサイズによっては、より高速な方法が線形になる場合があります。 このような検索を7つの数字の配列で繰り返し実行している場合は、パフォーマンスの違いがほとんど見られません。おそらく実際は遅いでしょう。

しかし、それよりも多くの配列を展開して、最初にバイナリ検索を行い、次にリニア検索を行う方が良いでしょう。

これを1回実行して範囲の下端部分をつかんで、線形にして範囲の終点を見つけます。

エンドポイントについて別のバイナリを実行することはできますが、単純な線形関数で平均化する必要があります。