Как преобразовать линейный поиск в бинарный поиск?

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

хорошо, понятно, почему значение не вставлено, это потому, что вы никогда не вставляли значение.Найдя индекс позиции для вставки, вы просто возвращаетесь из функции, ничего не делая.

Answer 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

}

Таким образом, когда вы оптимизируете / измените свою функцию поиска, ваша функция вставки тоже будет работать быстрее!

Как примечание, я думаю, что ваша функция поиска не даст вам ожидаемого поведения, как написано.Если у вас есть список [0,1,4,5,9] и я ищу 7, я получу индекс nElems (5), который может быть неверно истолкован, поскольку значения в индексах от 0 до 4 все меньше, чем7. Кажется немного шатким.

Answer 3

Вам нужно выполнить бинарный поиск, чтобы найти индекс вставки перед перемещением элементов. В последнем фрагменте кода вы пытаетесь использовать переменную curIn для перемещения элементов внутри цикла while до завершения двоичного поиска. Попробуйте переместить цикл for за пределы цикла while.

Answer 4

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