Collections.binarySearch用法
<DiversityScoreMapping> int java.util.Collections.binarySearch(List<? extends Comparable<? super DiversityScoreMapping>> list, DiversityScoreMapping key)
Searches the specified list for the specified object using the binary search algorithm. The list must be sorted into ascending order according to the natural ordering of its elements (as by the sort(List) method) prior to making this call. If it is not sorted, the results are undefined. If the list contains multiple elements equal to the specified object, there is no guarantee which one will be found.
This method runs in log(n) time for a "random access" list (which provides near-constant-time positional access). If the specified list does not implement the RandomAccess interface and is large, this method will do an iterator-based binary search that performs O(n) link traversals and O(log n) element comparisons.
Parameters:?
http://www.bianceng.cn/Programming/Java/200705/1581.htm
Java 1.2添加了自己的一套實用工具,可用來對數組或列表進行排列和搜索。這些工具都屬于兩個新類的“靜態”方法。這兩個類分別是用于排序和搜索數組的Arrays,以及用于排序和搜索列表的Collections。
1. 數組
Arrays類為所有基本數據類型的數組提供了一個過載的sort()和binarySearch(),它們亦可用于String和Object。下面這個例子顯示出如何排序和搜索一個字節數組(其他所有基本數據類型都是類似的)以及一個String數組:
//: Array1.java
// Testing the sorting & searching in Arrays
package c08.newcollections;
import java.util.*;
public class Array1 {
? static Random r = new Random();
? static String ssource =
??? "ABCDEFGHIJKLMNOPQRSTUVWXYZ" +
??? "abcdefghijklmnopqrstuvwxyz";
? static char[] src = ssource.toCharArray();
? // Create a random String
? public static String randString(int length) {
??? char[] buf = new char[length];
??? int rnd;
??? for(int i = 0; i < length; i++) {
????? rnd = Math.abs(r.nextInt()) % src.length;
????? buf[i] = src[rnd];
??? }
??? return new String(buf);
? }
? // Create a random array of Strings:
? public static
? String[] randStrings(int length, int size) {
??? String[] s = new String[size];
??? for(int i = 0; i < size; i++)
????? s[i] = randString(length);
??? return s;
? }
? public static void print(byte[] b) {
??? for(int i = 0; i < b.length; i++)
????? System.out.print(b[i] + " ");
??? System.out.println();
? }
? public static void print(String[] s) {
??? for(int i = 0; i < s.length; i++)
????? System.out.print(s[i] + " ");
??? System.out.println();
? }
? public static void main(String[] args) {
??? byte[] b = new byte[15];
??? r.nextBytes(b); // Fill with random bytes
??? print(b);
??? Arrays.sort(b);
??? print(b);
??? int loc = Arrays.binarySearch(b, b[10]);
??? System.out.println("Location of " + b[10] +
????? " = " + loc);
??? // Test String sort & search:
??? String[] s = randStrings(4, 10);
??? print(s);
??? Arrays.sort(s);
??? print(s);
??? loc = Arrays.binarySearch(s, s[4]);
??? System.out.println("Location of " + s[4] +
????? " = " + loc);
? }
} ///:~類的第一部分包含了用于產生隨機字串對象的實用工具,可供選擇的隨機字母保存在一個字符數組中。randString()返回一個任意長度的字串;而readStrings()創建隨機字串的一個數組,同時給定每個字串的長度以及希望的數組大小。兩個print()方法簡化了對示范數組的顯示。在main()中,Random.nextBytes()用隨機選擇的字節填充數組自變量(沒有對應的Random方法用于創建其他基本數據類型的數組)。獲得一個數組后,便可發現為了執行sort()或者binarySearch(),只需發出一次方法調用即可。與binarySearch()有關的還有一個重要的警告:若在執行一次binarySearch()之前不調用sort(),便會發生不可預測的行為,其中甚至包括無限循環。
對String的排序以及搜索是相似的,但在運行程序的時候,我們會注意到一個有趣的現象:排序遵守的是字典順序,亦即大寫字母在字符集中位于小寫字母的前面。因此,所有大寫字母都位于列表的最前面,后面再跟上小寫字母——Z居然位于a的前面。似乎連電話簿也是這樣排序的。
2. 可比較與比較器
但假若我們不滿足這一排序方式,又該如何處理呢?例如本書后面的索引,如果必須對以A或a開頭的詞條分別到兩處地方查看,那么肯定會使讀者頗不耐煩。
若想對一個Object數組進行排序,那么必須解決一個問題。根據什么來判定兩個Object的順序呢?不幸的是,最初的Java設計者并不認為這是一個重要的問題,否則就已經在根類Object里定義它了。這樣造成的一個后果便是:必須從外部進行Object的排序,而且新的集合庫提供了實現這一操作的標準方式(最理想的是在Object里定義它)。
針對Object數組(以及String,它當然屬于Object的一種),可使用一個sort(),并令其接納另一個參數:實現了Comparator接口(即“比較器”接口,新集合庫的一部分)的一個對象,并用它的單個compare()方法進行比較。這個方法將兩個準備比較的對象作為自己的參數使用——若第一個參數小于第二個,返回一個負整數;若相等,返回零;若第一個參數大于第二個,則返回正整數。基于這一規則,上述例子的String部分便可重新寫過,令其進行真正按字母順序的排序:
//: AlphaComp.java
// Using Comparator to perform an alphabetic sort
package c08.newcollections;
import java.util.*;
public class AlphaComp implements Comparator {
? public int compare(Object o1, Object o2) {
??? // Assume it's used only for Strings...
??? String s1 = ((String)o1).toLowerCase();
??? String s2 = ((String)o2).toLowerCase();
??? return s1.compareTo(s2);
? }
? public static void main(String[] args) {
??? String[] s = Array1.randStrings(4, 10);
??? Array1.print(s);
??? AlphaComp ac = new AlphaComp();
??? Arrays.sort(s, ac);
??? Array1.print(s);
??? // Must use the Comparator to search, also:
??? int loc = Arrays.binarySearch(s, s[3], ac);
??? System.out.println("Location of " + s[3] +
???? " = " + loc);
? }
} ///:~
通過造型為String,compare()方法會進行“暗示”性的測試,保證自己操作的只能是String對象——運行期系統會捕獲任何差錯。將兩個字串都強迫換成小寫形式后,String.compareTo()方法會產生預期的結果。
若用自己的Comparator來進行一次sort(),那么在使用binarySearch()時必須使用那個相同的Comparator。
Arrays類提供了另一個sort()方法,它會采用單個自變量:一個Object數組,但沒有Comparator。這個sort()方法也必須用同樣的方式來比較兩個Object。通過實現Comparable接口,它采用了賦予一個類的“自然比較方法”。這個接口含有單獨一個方法——compareTo(),能分別根據它小于、等于或者大于自變量而返回負數、零或者正數,從而實現對象的比較。下面這個例子簡單地闡示了這一點:
//: CompClass.java
// A class that implements Comparable
package c08.newcollections;
import java.util.*;
public class CompClass implements Comparable {
? private int i;
? public CompClass(int ii) { i = ii; }
? public int compareTo(Object o) {
??? // Implicitly tests for correct type:
??? int argi = ((CompClass)o).i;
??? if(i == argi) return 0;
??? if(i < argi) return -1;
??? return 1;
? }
? public static void print(Object[] a) {
??? for(int i = 0; i < a.length; i++)
????? System.out.print(a[i] + " ");
??? System.out.println();
? }
? public String toString() { return i + ""; }
? public static void main(String[] args) {
??? CompClass[] a = new CompClass[20];
??? for(int i = 0; i < a.length; i++)
????? a[i] = new CompClass(
??????? (int)(Math.random() *100));
??? print(a);
??? Arrays.sort(a);
??? print(a);
??? int loc = Arrays.binarySearch(a, a[3]);
??? System.out.println("Location of " + a[3] +
???? " = " + loc);
? }
} ///:~
當然,我們的compareTo()方法亦可根據實際情況增大復雜程度。
3. 列表
可用與數組相同的形式排序和搜索一個列表(List)。用于排序和搜索列表的靜態方法包含在類Collections中,但它們擁有與Arrays中差不多的簽名:sort(List)用于對一個實現了Comparable的對象列表進行排序;binarySearch(List,Object)用于查找列表中的某個對象;sort(List,Comparator)利用一個“比較器”對一個列表進行排序;而binarySearch(List,Object,Comparator)則用于查找那個列表中的一個對象(注釋⑨)。下面這個例子利用了預先定義好的CompClass和AlphaComp來示范Collections中的各種排序工具:
//: ListSort.java
// Sorting and searching Lists with 'Collections'
package c08.newcollections;
import java.util.*;
public class ListSort {
? public static void main(String[] args) {
??? final int SZ = 20;
??? // Using "natural comparison method":
??? List a = new ArrayList();
??? for(int i = 0; i < SZ; i++)
????? a.add(new CompClass(
??????? (int)(Math.random() *100)));
??? Collection1.print(a);
??? Collections.sort(a);
??? Collection1.print(a);
??? Object find = a.get(SZ/2);
??? int loc = Collections.binarySearch(a, find);
??? System.out.println("Location of " + find +
???? " = " + loc);
??? // Using a Comparator:
??? List b = new ArrayList();
??? for(int i = 0; i < SZ; i++)
????? b.add(Array1.randString(4));
??? Collection1.print(b);
??? AlphaComp ac = new AlphaComp();
??? Collections.sort(b, ac);
??? Collection1.print(b);
??? find = b.get(SZ/2);
??? // Must use the Comparator to search, also:
??? loc = Collections.binarySearch(b, find, ac);
??? System.out.println("Location of " + find +
???? " = " + loc);
? }
} ///:~ ⑨:在本書寫作時,已宣布了一個新的Collections.stableSort(),可用它進行合并式排序,但還沒有它的測試版問世。
這些方法的用法與在Arrays中的用法是完全一致的,只是用一個列表代替了數組。
TreeMap也必須根據Comparable或者Comparator對自己的對象進行排序。
本文來自-編程入門網:http://www.bianceng.cn/Programming/Java/200705/1581.htm
?
總結
以上是生活随笔為你收集整理的Collections.binarySearch用法的全部內容,希望文章能夠幫你解決所遇到的問題。