在java中的遞歸二進制搜索中的hi，hi索引

對於java字符串數組上的經典binarySearch（比如String[] a），這是調用搜索方法的正確方法嗎？是在java中的遞歸二進制搜索中的hi，hi索引

binarySearch(a,key,0,a.length)

或

我都嘗試了以下實施，都似乎工作..有一個用例，其中這兩種調用可能會失敗？

class BS{ 
    public static int binarySearch(String[] a,String key){ 
     return binarySearch(a,key,0,a.length); 
     //return binarySearch(a,key,0,a.length-1); 
    } 
    public static int binarySearch(String[] a,String key,int lo,int hi) { 
     if(lo > hi){ 
      return -1; 
     } 
     int mid = lo + (hi - lo)/2; 
     if(less(key,a[mid])){ 
      return binarySearch(a,key,lo,mid-1); 
     } 
     else if(less(a[mid],key)){ 
      return binarySearch(a,key,mid+1,hi); 
     } 
     else{ 
      return mid; 
     } 

    } 
    private static boolean less(String x,String y){ 
     return x.compareTo(y) < 0; 
    } 
    public static void main(String[] args) { 
     String[] a = {"D","E","F","M","K","I"}; 
     Arrays.sort(a); 
     System.out.println(Arrays.toString(a)); 
     int x = binarySearch(a,"M"); 
     System.out.println("found at :"+x); 

    } 
}

來源

2013-08-26 damon

最穩定的方法是'Arrays.binarySearch（a，「M」）'。他們對代碼進行了多次測試，然後我們可以測試我們的代碼。 – jboi

考慮其中

一個= [ 「foo」的]

和你搜索鍵「動物園」與binarySearch(a,key,0,a.length);

該代碼將在區間[0,1]爲它查詢的情況下，看到它應該比對，下一遞歸搜索區間[1,1]，從而導致產生了一個AR的[1]在線路

if(less(key,a[mid])){

索引ray出界限錯誤。

第二種解決方案將正常工作。

來源

2013-08-26 05:47:16 Lake

我認爲第二種方法是安全的。

考慮這種情況 - 您有一個由9個元素組成的數組，鍵位於最後一個索引（第8元素）。那麼你可能有這樣的方法調用如果按照第一種方法 -

binarySearch(a, key, 9, 9);

現在，在方法執行，在下面的行整數除法將導致9 -

int mid = 9 + (9 - 9)/2;

和你會被索引9陣列中的下一行 -

if(less(key,a[mid])) { // You'll face ArrayIndexOutOfBoundException 
    .... 
}

這將是無效的，並導致ArrayIndexOutOfBoundException。

然而，第二種方法將會很好。

來源

2013-08-26 05:39:50

在java中的遞歸二進制搜索中的hi，hi索引

回答

相關問題