Java遞歸二進制搜索拋出界限異常？

嗨，我被要求在大學爲我的數據結構類編寫一個遞歸二進制搜索，但是我遇到了一個小問題。當我搜索一個超出範圍的數字（在這種情況下超過10）時，它會拋出一個超出界限的異常。我明白爲什麼它會這樣做，因爲陣列沒有> 10個空格，但我不知道如何解決它。有任何想法嗎？Java遞歸二進制搜索拋出界限異常？

即時搜索的數組是一個有序數組1 - 10（索引0 - 9）。

public int recursiveBinarySearch(int[] anArray, int searchedNumber, int min, int max) { 

    if (min > max) 
     { 
       System.out.println(searchedNumber + " is not present in tha array."); 
       //return -1 to show that the value has not been found 
     return -1; 
     } 
     // find the centre of the array 
     int centre = (min + max)/2; 

    if (anArray[centre] == searchedNumber) 
     { 
       System.out.println(searchedNumber + " was found at index " + centre); 
     return centre; 
     } 

     if (anArray[centre] < searchedNumber) 
     { 
     return recursiveBinarySearch(anArray, searchedNumber, centre+1, max); 
     } 

     return recursiveBinarySearch(anArray, searchedNumber, min, centre-1); 

}

來源

2010-10-25 Rvddps

二分查找不應該使用/ 2它應該使用按位>>。 – Woot4Moo 2010-10-25 17:35:08

其實它應該使用>>>。 – helpermethod 2010-10-25 18:12:14

爲什麼？你不在乎比特是什麼樣子。你在乎數字是什麼（以及它的一半是什麼）。這種優化應該留給編譯器/ jvm。 – ILMTitan 2010-10-25 19:07:58

public int recursiveBinarySearch(...) { 
    if (max >= array.length) { 
     max = array.length - 1; 
    } 
    if (min < 0) { 
     min = 0; 
    } 
    ... rest of the code 
}

PS不是一個nagger，但我也建議使用一致的縮進。相信我，它對編寫無bug程序有很大的幫助。

來源

2010-10-25 17:20:43

非常感謝，這正是我需要的。至於縮進，感謝您指出它，我的程序的其餘部分是縮進..只是不是由於某種原因這種方法。再次感謝。 – Rvddps 2010-10-25 17:23:57

我想這與min = 0和max = 9開始，然後它

min = 0, max = 9, c = (0+9/2) = 4 
min = 5, max = 9, c = (6+9/2) = 7 
min = 8, max = 9, c = (8+9/2) = 8 
min = 9, max = 9, c = (9+9/2) = 9 
min = 10, max = 9, ...

正如你可以看到它越過邊界，min = 10當然會引起問題。爲了避免剛剛拓寬初始條件：

if (min > max || min > Array.length -1 || max < 0) 
    // not found!

因此，如果您打算在陣列上任意兩個方向，則請求的元素不會被發現。

來源

2010-10-25 17:26:53 Jack

爲什麼會導致問題？他在'if（min> max）'中注意了這一點 – codaddict 2010-10-25 17:29:34

Java遞歸二進制搜索拋出界限異常？

回答

相關問題