5

整数のソートされた配列があります：

{1,2,4,4,5,8,12,15,15,23,54}

その配列内の数が範囲、たとえば4と15の間にあるかどうかを調べたいと思います。

{4,4,5,6,12,15,15}

したがって、その範囲内にある配列には7つのアイテムがあります。

これはO（log（N））時間で行う必要があり、二分探索を使用できると思いましたが、重複しているため、下限と上限が見つかりませんでした。

これをO（log（N））時間でどのように行うことができますか？

私は前からループし、次に最後からループすることを考えましたが、それはO（N）までである可能性があります

4

4 に答える 4

0

あなたがそれを改善することができるのであれば、私はJavaでコードを与えたと説明していません。

 public class Test {

public static int binSearch(int array[], int key, int left, int right,boolean lb)
{
int mid = left + (right-left)/2;
if (key < array[mid])
    return binSearch(array, key, left, mid-1,lb);
else if (key > array[mid])
    return binSearch(array, key, mid+1, right,lb);
else if (key == array[mid]){
    if(!lb){
    if(key==array[mid+1]){
        int ctr=mid+1;
        while(key==array[++ctr]);
        return ctr--;
      }
    else
        return mid;
    }
    else{
    if(key==array[mid-1]){
        int ctr=mid-1;
        while(key==array[--ctr]);
        return ctr++;
    }
    else
        return mid;
   }

}
return -0; // Not Found

}

public static void main(String[] args) {
int a[]={1,2,4,4,5,8,12,15,15,23,54};
int start=binSearch(a, 4, 0, a.length,true);
int end=binSearch(a, 15, 0, a.length,false);
System.out.println(end-start+1);// number are include
}

}

于 2013-03-08T11:40:03.957 に答える
0

二分探索では、必要な数が見つかったとき、またはその数がリストにないときに、再帰手順を停止します。
ここでは、二分探索アルゴリズムを変更する必要があります。より低い範囲から始めて、aより小さい数値が見つかるまで繰り返します。これを行っている間、 lowとhighという 2 つのインデックスを維持します。比較している数値が 未満の場合は、低く更新し、そうでない場合は高く更新します。より低いインデックスが得られたので、この手順を再帰的に適用して、これよりも大きい数を見つけますa。このインデックスは、開始インデックスを提供します。 ここで、上位範囲の補完を行うと、終了インデックスが得られます。 答えは

ending index - starting index + 1

imin = 0, imax = A.size()-1
low = 0, high = A.size()-1
while(imax >= imin)
{
   imid = mid(imin,imax)
   if(key < A[imid])
   {
       imax = imid -1
       high = imid
   }
   else if(key > A[imid])
   {
       imin = imid + 1
       low = imid
   }
   else 
   {
       high = imid
       break;
   }
 }

ここで、ループから抜けたらimin > imax、 if をチェックします。yes の場合、下限の範囲インデックスは imax になります。それ以外の場合は、条件に達するまで、同じキーを使用しimin = lowて検索を繰り返します。上限レンジについても同じことを繰り返します。 時間計算量は～imax = highimin > imax
O(log(n))O(n)

于 2013-03-08T11:04:06.790 に答える
0

要素の最初または最後の出現を見つけるかどうかのパラメーターを持つ、修正された二分探索が必要です。
変更された binsearch を自分で作成する必要があります。

于 2013-03-08T11:14:23.010 に答える