如何将线性搜索转换为二进制搜索？

Question

- 这是我使用二进制搜索算法的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

使用有序数组.

Answer 1

好吧,很明显为什么没有插入值,这是因为你从未插入过值.一旦找到要插入的位置索引,只需从函数返回而不做任何操作.