/**
  227        * Searches the specified list for the specified object using the binary
  228        * search algorithm.  The list must be sorted into ascending order
  229        * according to the {@linkplain Comparable natural ordering} of its
  230        * elements (as by the {@link #sort(List)} method) prior to making this
  231        * call.  If it is not sorted, the results are undefined.  If the list
  232        * contains multiple elements equal to the specified object, there is no
  233        * guarantee which one will be found.
  234        *
  235        * <p>This method runs in log(n) time for a "random access" list (which
  236        * provides near-constant-time positional access).  If the specified list
  237        * does not implement the {@link RandomAccess} interface and is large,
  238        * this method will do an iterator-based binary search that performs
  239        * O(n) link traversals and O(log n) element comparisons.
  240        *
  241        * @param  list the list to be searched.
  242        * @param  key the key to be searched for.
  243        * @return the index of the search key, if it is contained in the list;
  244        *         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The
  245        *         <i>insertion point</i> is defined as the point at which the
  246        *         key would be inserted into the list: the index of the first
  247        *         element greater than the key, or <tt>list.size()</tt> if all
  248        *         elements in the list are less than the specified key.  Note
  249        *         that this guarantees that the return value will be &gt;= 0 if
  250        *         and only if the key is found.
  251        * @throws ClassCastException if the list contains elements that are not
  252        *         <i>mutually comparable</i> (for example, strings and
  253        *         integers), or the search key is not mutually comparable
  254        *         with the elements of the list.
  255        */
  256       public static <T>
  257       int binarySearch(List<? extends Comparable<? super T>> list, T key) {
  258           if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
  259               return Collections.indexedBinarySearch(list, key);
  260           else
  261               return Collections.iteratorBinarySearch(list, key);
  262       }