二进制搜索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; 
     } 
}