Collections.binarySearch如何工作？

我想了解Collections.binarySearch如何在Java中工作。我不太明白我得到的輸出。Collections.binarySearch如何工作？

public static void main(String args[]) { 
     // create arraylist  
     ArrayList<String> arlst=new ArrayList<String>(); 


     arlst.add("A"); 
     arlst.add("D"); 
     arlst.add("C"); 
     arlst.add("B"); 
     arlst.add("E"); 

     int index=Collections.binarySearch(arlst, "D", Collections.reverseOrder());  

     System.out.println(index); 


    }  
}

此代碼的輸出爲-1。

而當元素已經在這個順序

 arlst.add("D"); 
     arlst.add("E"); 
     arlst.add("C"); 
     arlst.add("B"); 
     arlst.add("A");

被插入，我得到0的結果。如果元素沒有找到，我認爲負數是一個結果。任何人都可以澄清我收到的結果嗎？

來源

2015-06-07 Nat

你知道二進制搜索一般是如何工作的嗎？ – Tom

有關類jdk用法的所有有用信息通常是以下文檔：「使用二分搜索算法在指定列表中搜索指定對象。該列表必須根據其元素的自然順序按升序排序（如通過sort（List）方法），如果它沒有排序，結果是未定義的。如果列表包含多個元素等於指定的對象，則不能保證哪個元素會被找到。「 – davidxxx

@davidh，你引用了錯誤的bynarySearch方法，但是OP使用了一個以Comparator作爲參數的引用 – aioobe

您的數據必須根據給定的比較器進行排序，以便二進制搜索按預期工作。（如果它不是，該行爲是未定義。）

列表必須根據指定的比較器（如由sort(List, Comparator)方法）在進行此調用之前被按升序排列。

如果數據確實排序，該方法將返回尋求元素的索引（如果它的發現），否則(-(insertion point) - 1)，爲the documentation規定。

例子：

// Make sure it's sorted 
Collections.sort(arlst, Collections.reverseOrder()); 

int index=Collections.binarySearch(arlst, "D", Collections.reverseOrder());  

System.out.println(index); // prints 1

來源

2015-06-07 13:42:00 aioobe

因此，二分查找需要有序數組才能按預期工作，這是正確的嗎？這個東西，試圖弄清楚它是如何工作的 – Nat

是的，在這種情況下，既然你是usi ng'Collections.reverseOrder'它需要被分類爲'E'，'D'，'C'，'B'，'A'。 – aioobe

明白了！非常感謝！這看起來很混亂，但實際上非常簡單。 – Nat

只是爲了使其更清晰 - 爲什麼輸出是-1。是的，你沒有先排序是一個大錯誤。但這裏還有其他一些事情要清楚。

作爲@aioobe在他的答案中提到，但他沒有說清楚，但我認爲。 (-(insertion point) - 1)是什麼意思？這是醫生說的。

檢索關鍵字的索引，如果它包含在列表中;否則，（ - （插入點） - 1）。插入點定義爲密鑰將插入列表的位置：大於密鑰的第一個元素的索引或list.size（）如果列表中的所有元素都小於指定的鍵。請注意，這保證返回值將大於等於0當且僅當找到密鑰。

因此，爲了使答案更加明確：-1 = -0 - 1

我想在這裏強調的是，輸出可能-2或-3或什麼的。因爲如果列表中的所有元素都小於指定鍵，則輸出將是-list.size() - 1。

來源

2017-02-16 02:20:15

Collections.binarySearch如何工作？

回答

相關問題