使用二進制搜索算法作爲實現二進制插入的基礎

Question

我試圖實現二進制插入方法。

目前這個方法非常簡單，它需要一個參數，在while循環中它搜索一個比參數大的元素（在這個例子中是一個字符串，它是一個人的姓氏），它會中斷一次它會找到它並將其餘的數組移到右側。然後將參數插入到分解位置。

我試圖將其更改爲通過從二進制搜索算法中借用來搜索插入位置的程序。但是，我無法讓它工作。

您能否讓我知道我做錯了什麼？這裏是我的代碼：

 
public void insert(Person person) 
{
 

String lastName = person.getLastName(); 

    int position = -1; // the position from which the array will be shifted to the right and where the argument will be inserted, will be assigned properly below 

    int lowerBound = 0; 
    int upperBound = numElems - 1; 
    int currIt; 

    if (numElems == 0) 
     array[0] = person; // if array empty insert at first position 
    else 
    { 
     while (true) 
     { 
      currIt = (lowerBound + upperBound)/2; //the item to compare with 

      int result2 = 0; 

      int result1 = array[currIt].getLastName().compareTo(lastName); 

      if (array[currIt+1] != null) // if the next element is not null, compare the argument to it 
       result2 = array[currIt+1].getLastName().compareTo(lastName); 

      if (currIt == 0 && result1 > 0) // this is when the argument is smaller then the first array element 
      { 
       position = 0; 
       break; 
      } 
      // if the position to insert is the last one, or we have found a suitable position between a smaller and a bigger element 
      else if ( (result1 < 0 && (currIt == numElems-1)) || (result1 < 0 && result2 > 0) ) { 
       position = currIt+1;    
       break; 
      }  
      else 
      { 
       if (result1 < 0) // the place to put it should be in the upper half 
        lowerBound = currIt + 1; 
       else 
        upperBound = currIt - 1; //in the lower half    
      } 

     } 
    } 
    // position has been set to anything else other -1, then we have found our spot, probably a redundant check but useful for debugging 
    if (position != -1) 
    { 
     //shift array to the right and insert element 
     for (int j = numElems; j > position; j--) 
     array[j] = array[j-1]; 
     System.out.println("Inserted an element"); 
     array[position] = person; 
     numElems++; 
    } 

} 

Answer 1

你 「大概[]冗餘校驗」 禁止初期插入。位置是第一次。

在頂部設置position到0應該解決問題。