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()

我需要修改 insert() 方法以使用 find() 方法的二进制搜索算法。到目前为止,这是我想出的。显然它有问题,但我似乎无法找到问题所在。它根本不起作用,即不执行插入:

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

您需要在移动元素之前执行二进制搜索以找到插入索引。在您的最后一个代码片段中,您尝试在二进制搜索完成之前使用该变量在循环curIn内移动元素。while尝试将循环移到for循环之外while

于 2010-09-22T04:18:18.757 回答
2

嗯,为什么不直接调用你的 find 函数呢?

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 回答
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 回答