確實Arrays.BinarySearch要求該陣列被以升序

排序根據文檔：確實Arrays.BinarySearch要求該陣列被以升序

public static <T> int binarySearch(T[] a, T key, Comparator<? super T> c)

搜索使用二進制搜索算法指定的對象指定的數組。

數組必須根據指定的比較（如通過sort（T []，比較器）方法）之前在進行此調用被按升序排列。

如果沒有排序，結果是未定義的。如果數組包含與指定對象相同的多個元素，則不會保證哪一個會被找到。

上述是否意味着當陣列在升序順序排序，才能使用該方法Arrays.binarySearch？

我測試如下所示

class Unturned { 
    public static void main(String[] args) { 
     String[] chars = {"a", "b", "c", "e","f","h","i"}; 
     MySort ms = new MySort(); 

     Arrays.sort(chars, ms); 
     for(String c : chars) System.out.print(c + " "); 

     System.out.println("\n" + Arrays.binarySearch(chars, "d", ms)); 
    } 
    static class MySort implements Comparator<String> { 
     public int compare(String a, String b) { 
      return b.compareTo(a); 
} } }

輸出：

i h f e c b a 
-5

-5把插入點與值c的元件，其是正確的。（即-4-1）。
爲什麼說文檔說數組必須按升序排序？

來源

2012-01-02 ziggy

每個比較器定義給定類型的元素的排序。要求僅僅是數組元素必須被排序，使得對於<的某些有效定義，a [0] < ... < a [n-1]。該定義不必與我們對於例如<的常規概念相對應。數字 - 實際上，它甚至可以被定義爲傳統的>。

來源

2012-01-02 18:34:32

我覺得這讓我很困惑。我把這個描述解釋爲意味着比較器應該按升序對值進行排序，即a [0] <... ziggy 2012-01-02 18:43:58

它說：「必須根據指定的比較器按升序排列」。粗體的部分是關鍵部分;你的數組的確是根據指定的比較器進行排序的（因爲你剛剛排序！）。

來源

2012-01-02 18:28:30

它要求所有元素都根據比較器的實現方式增加。例如你使用一個反向比較器，所有的元素必須以相反的順序。

爲什麼文檔說數組必須按升序排序？

二分查找基於此假設工作。 http://en.wikipedia.org/wiki/Binary_search_algorithm當它比較中間元素時，它可以假設如果它大於那個元素，它也比中間之前的所有元素都大。如果數組沒有特定的順序，它將不得不搜索整個數組，也稱爲蠻力搜索。

來源

2012-01-02 18:28:50

確實Arrays.BinarySearch要求該陣列被以升序

回答

相關問題