二進制搜索變量（Java）中的無限循環

Question

我的目標是輸入一個鍵和一個數組，然後使用二分查找輸出該數組中小於或等於該鍵的值的數目。

這是我的代碼：

import java.util.*; 
import java.io.*; 

public class search { 
    public static void main(String[] args) { 
     Scanner scan = new Scanner(System.in); 
     int key = scan.nextInt(); 
     int size = scan.nextInt(); 
     int [] array = new int [size]; 

     for (int i = 0;i < size ;i++) { 
      array[i] = scan.nextInt(); 
     } 
     Arrays.sort(array); 

     System.out.println(binary(key, array)); 
    } 

    public static int binary (int key, int [] array){ 
     int lo = 0; 
     int hi = array.length - 1; 

     while (lo < hi){ 
      int mid = (lo + hi)/2; 
      if (array[mid] <= key){ 
       lo = mid; 
      } 

      else { 
       hi = mid - 1; 
      } 
     } 

     return lo + 1; 
    } 
} 

隨着數據密鑰= 5，陣列= {2,4,6,7}，程序正常工作。但目前有三個的值小於或等於該鍵值，它就會出現亂碼。例如，key = 5，array = {2,4,5,6}會產生一個無限循環。我找到了這個原因，但我沒有看到如何解決它。

基本上mid值一直以相同的值計算。我能做些什麼來解決這個問題？如果代碼本身是錯誤的，那麼這意味着the set solution for a USACO problem是錯誤的。

Answer 1

樣品溶液似乎罰款。您的代碼的問題是mid = (lo + hi)/2轉向lo，這是一個問題，因爲更新案例是lo = mid和hi = mid - 1。當hi == lo + 1，在第一種情況下，沒有進展。你應該整理一下樣本：mid = (lo + hi + 1)/2（警告：可能會在長陣列上溢出;檢查你的約束）。

該示例還檢查第一個值是否小於該鍵。

Answer 2

你的算法看起來不錯。但是我發現在爲mid賦值時存在一個問題。

int mid = (hi+lo)/2 

思的情況下，其中的

hi=4 
mid = 3 

現在爲中間的新值將是（3 + 4）/ 2 = 3（整數除法）

因此該循環將繼續無間斷地運行。

在這種情況下，您可以通過檢查此條件來增加mid的值。

但更有效的是，它似乎更好的檢查中期重複的價值，然後打破循環。 最後檢查是否數組的值[喜]相同的陣列[MID]

希望這將有助於..

有一個愉快的一天.. :)

編輯

做的更好的方式是

while循環更改爲

while(mid<hi+1){ 
} 

然後檢查循環之後的值相等.​​.

OR 只需設置

mid = (mid+hi+1)/2 

Answer 3

在你的循環，你必須使你的時間間隔越來越小，你也必須排除你只是看着元素。當你離開的時候你會這樣做，但是當你走的時候不會。

你也錯過了長度爲1的區間，因爲你用包容的上限和下限。你的循環條件應該是lo <= hi。

最後，返回太多了：結果應該是0的時候，關鍵是比第一元件小而且它應該是數組的長度時，它比最後一個元素更大。

所以：

static int binary(int key, int[] array) 
{ 
    int lo = 0; 
    int hi = array.length - 1; 

    while (lo <= hi) { 
     int mid = (lo + hi)/2; 

     if (array[mid] <= key) { 
      lo = mid + 1; 
     } else { 
      hi = mid - 1; 
     } 
    } 

    return lo; 
} 

在我看來，最好是使用獨佔上限，因爲Java通常不會。 （例如，一個長度爲n的數組的元素在插入0到n - 1之間，上限n在有效範圍之外。）如果沒有其他值，它將與其他Java代碼一致。所以：

static int binary(int key, int[] array) 
{ 
    int lo = 0; 
    int hi = array.length; 

    while (lo < hi) { 
     int mid = (lo + hi)/2; 

     if (array[mid] <= key) { 
      lo = mid + 1; 
     } else { 
      hi = mid; 
     } 
    } 

    return lo; 
}