源码如下：
1 /** 2 * Searches the specified list for the specified object using the binary 3 * search algorithm. The list must be sorted into ascending order 4 * according to the {@linkplain Comparable natural ordering} of its 5 * elements (as by the {@link #sort(List)} method) prior to making this 6 * call. If it is not sorted, the results are undefined. If the list 7 * contains multiple elements equal to the specified object, there is no 8 * guarantee which one will be found. 9 * 10 * <p>This method runs in log(n) time for a "random access" list (which 11 * provides near-constant-time positional access). If the specified list 12 * does not implement the {@link RandomAccess} interface and is large, 13 * this method will do an iterator-based binary search that performs 14 * O(n) link traversals and O(log n) element comparisons. 15 * 16 * @param list the list to be searched. 17 * @param key the key to be searched for. 18 * @return the index of the search key, if it is contained in the list; 19 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The 20 * <i>insertion point</i> is defined as the point at which the 21 * key would be inserted into the list: the index of the first 22 * element greater than the key, or <tt>list.size()</tt> if all 23 * elements in the list are less than the specified key. Note 24 * that this guarantees that the return value will be >= 0 if 25 * and only if the key is found. 26 * @throws ClassCastException if the list contains elements that are not 27 * <i>mutually comparable</i> (for example, strings and 28 * integers), or the search key is not mutually comparable 29 * with the elements of the list. 30 */ 31 32 private static final int BINARYSEARCH_THRESHOLD = 5000;//二分查找的阈值 33 34 public static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key) { 35 if(list instanceof RandomAccess || list.size() < BINARYSEARCH_THRESHOLD)//RandomAccess，是一个接口，用来标记一个list是支持高性能随机访问的 36 return Collections.indexedBinarySearch(list, key); 37 else 38 return Collections.iteratorBinarySearch(list, key); 39 } 40 41 private static <T> int indexedBinarySearch(List<? extends Comparable<? super T>> list, T key) { 42 int low = 0; 43 int high = list.size() - 1; 44 while(low <= high) { 45 int mid = (low + high) >>> 1;//>>> 无符号右移，空位补0;右移一位，相当于除以2，但右移的运算速度更快，若使用(low+high)/2求中间位置容易溢出 46 Comparable<? super T> midVal = list.get(mid); 47 int cmp = midVal.compareTo(key); 48 49 if(cmp < 0) 50 low = mid + 1; 51 else if(cmp > 0) 52 high = mid - 1; 53 else 54 return mid;//key found 55 } 56 return -(low + 1);//key not found 57 } 58 59 private static <T> int iteratorBinarySearch(List<? extends Comparable<? super T>> list, T key) { 60 int low = 0; 61 int high = list.size() - 1; 62 ListIterator<? extends Comparable<? super T>> i = list.listInterator(); 63 while (low <= high) { 64 int mid = (low + high) >>> 1; 65 Comparable<? super T> midVal = get(i, mid); 66 int cmp = midVal.compareTo(key); 67 68 if(cmp < 0) { 69 low = mid + 1; 70 } else if(cmp > 0) { 71 high = mid - 1; 72 } else { 73 return mid;// key found 74 } 75 } 76 return -(low + 1);// key not found 77 }
注：
（1）list需先按照升序排好;
（2）如果list中有重复的元素，结果是不确定的;
（3）List<? extends Comparable<? super T>>，java泛型，<? extends T> 表示类型的上界，表示参数的类型的可能是T或是T的子类；<? super T> 表示类型的下界，表示参数的类型是此类型T的父类型，直至Object;