二進制搜索Java實現算法

Question

我需要實現二進制搜索算法幫助，誰能告訴我什麼是錯我的代碼：

public int bsearch(Item idToSearch) { 
    int lowerBoundary = 0; 
    int upperBoundary = myStore.size() - 1; 
    int mid = -1; 

    while(upperBoundary >= lowerBoundary) { 
     mid = (lowerBoundary + upperBoundary)/2; 

     //if element at middle is less than item to be searched, than set new lower boundary to mid 
     if(myStore.get(mid).compareTo(idToSearch) < 0) { 
      lowerBoundary = mid - 1; 
     } else { 
      upperBoundary = mid + 1; 
     } 
    } //end while loop 

    if(myStore.get(mid).equals(idToSearch)) { 
     return mid; 
    } else { 
     return -1; // item not found 
    } 
} // end method 

Answer 1

我想你的時候更新lowerBoundary和upperBoundary犯了一個錯誤。

它可能是：

if(myStore.get(mid).compareTo(idToSearch) < 0){ 
     lowerBoundary = mid + 1; 
    } else { 
     upperBoundary = mid - 1; 
    } 

而且你爲什麼不打破循環，如果你發現在mid元素？

Answer 2

我會

• 停止時的下限和上限是相同的。
• 當您發現匹配時停止
• 使用mid = (hi + lo) >>> 1;避免溢出導致錯誤。
• 閱讀JDK中的代碼，因爲它可以正常工作。

Answer 3

的第一個問題是邊界，也應停止的情況下，他找到了價值，但他並不導致可能的疏忽。

while(upperBoundary >= lowerBoundary) 
{ 
     mid = (lowerBoundary + upperBoundary)/2; 

     if (myStore.get(mid).equals(idToSearch)) break; // goal 

     if(myStore.get(mid).compareTo(idToSearch) < 0) 
     { 
      lowerBoundary = mid + 1; 
     } 
     else 
     { 
      upperBoundary = mid - 1; 
     } 
}