0

-これは、バイナリ検索アルゴリズムを使用した私のfind（）メソッドです。

  • 期待どおりに機能します。全く問題ありません。

    public int find(long searchKey) {
int lowerBound = 0;
int upperBound = nElems - 1;
int currentIndex;

while(true) {
    currentIndex = (lowerBound + upperBound) / 2;
    if(a[currentIndex] == searchKey)
        return currentIndex; // found it!
    else if(lowerBound > upperBound)
        return nElems; // can't find it
    else { // so then divide range
        if(a[currentIndex] < searchKey)
            lowerBound = currentIndex + 1; // it's in upper half
        else
            upperBound = currentIndex - 1; // it's in lower half
    } // end else divide range
} // end while loop
} // end find() method

これが線形検索を使用した元のinsert（）メソッドです。かなり簡単ですよね？

public void insert(long value) { // put element into array
    int j;
    for(j=0; j<nElems; j++) // find where it goes
        if(a[j] > value) // (linear search)
            break;
    for(int k=nElems; k>j; k--) // move bigger ones up
        a[k] = a[k-1];
    a[j] = value; // insert it
    nElems++; // increment size
} // end insert()

find（）メソッドのバイナリ検索アルゴリズムを使用するようにinsert（）メソッドを変更する必要があります。これが私がこれまでに思いついたものです。明らかに何か問題がありますが、問題を見つけることができないようです。まったく機能しません。つまり、挿入は実行されません。

public int insertBS(long value) {
    int lowerBound = 0;
    int upperBound = nElems - 1;
    int curIn;

    while(true) {
        curIn = (lowerBound + upperBound) / 2;
        if(a[curIn] == value)
            return curIn;
        else if(lowerBound > upperBound)
            return nElems;
        else {
            if(a[curIn] < value)
                lowerBound = curIn + 1;
            else
                upperBound = curIn - 1;
        }

        for(int k=nElems; k>curIn; k--) // move bigger one up
            a[k] = a[k-1];
        a[curIn] = value; 
        nElems++; 
    }
}

言語：Java

順序付き配列を使用します。

4

4 に答える 4

5

値が挿入されない理由は明らかです。値を挿入していないからです。挿入する位置のインデックスを見つけたら、何もせずに単に関数から戻ります。

于 2010-09-22T04:17:57.070 に答える
2

ええと、なぜあなたの検索機能を呼び出すだけではないのですか？

public int insertBS(long value) {
    int curIn = find(value); // find where it goes (binary search)
    for(int k=nElems; k>curIn; k--) // move bigger one up
        a[k] = a[k-1];
    a[j] = value; // insert it
    nElems++; // increment size

}

このように、検索関数を最適化/変更すると、挿入関数も高速になります。

ちなみに、あなたのfind関数は、書かれているように、期待される動作を提供しないと思います。[0,1,4,5,9]のリストがあり、7を検索すると、nElems（5）のインデックスが取得されます。これは、インデックス0〜4の値がすべてより小さいため、誤解される可能性があります。 7.少し不安定なようです。

于 2010-09-22T04:33:25.173 に答える
2

要素を移動する前に、バイナリ検索を実行して挿入インデックスを見つける必要があります。最後のコード スニペットでは、二分探索が完了する前に変数を使用しcurInてループ内の要素を移動しようとしています。ループをループの外にwhile移動してみてください。forwhile

于 2010-09-22T04:18:18.757 に答える
0 
int lowerBound = 0;
int upperBound = nElems-1;


int pos = 0;

if(value < a[0])
 pos=0;
else if(nElems>0 && value>a[upperBound])
 pos=nElems;
else
{
 while(nElems>1)
 {
  int j = (lowerBound + upperBound ) / 2;

  if(upperBound - lowerBound ==0)
  {
   pos = lowerBound+1;
   break;              // found it
      }
  else if(upperBound - lowerBound ==1)
  {
   pos=upperBound;  //lo encontre
   break;
  }
  else                          // divide range
          {
           if(a[j] < value)
               lowerBound = j + 1; // it's in upper half
       else
           upperBound = j - 1; // it's in lower half
      }  // end else divide range
 }
}


 for(int k=nElems; k>pos; k--)    // move higher ones up
    a[k] = a[k-1];
 a[pos] = value;                  // insert it
     nElems++;                      // increment size
于 2012-10-03T16:32:35.967 に答える