Javaコレクションにおける二分検索アルゴリズムの実装

Javaコレクションにおける二分検索アルゴリズムの実装
Arrays.binarySearchは秩序配列の特定区間の二分検索を実現し、簡単だと思いますが、ソースコードを読むと、これらのライブラリを実現する優れたテクニックが見え、常に完璧さと効率を追求しています.
学ぶべき点は次のとおりです.
(1)境界検査;
(2)中位数を求める場合はx/2ではなくシフト操作を用いる.
(3)検索された要素が配列内にない場合、戻り値によって挿入すべき位置が示され、直接-1を返すのではなく、戻り値によって挿入すべき位置が示される.
public static int binarySearch(int[] a, int fromIndex, int toIndex,
                                   int key) {
        rangeCheck(a.length, fromIndex, toIndex);
        return binarySearch0(a, fromIndex, toIndex, key);
    }
   //Like public version, but without range checks.
    private static int binarySearch0(int[] a, int fromIndex, int toIndex,
                                     int key) {
        int low = fromIndex;
        int high = toIndex - 1;
        while (low <= high) {
            int mid = (low + high) >>> 1;
            int midVal = a[mid];
            if (midVal < key)
                low = mid + 1;
            else if (midVal > key)
                high = mid - 1;
            else
                return mid;//key found
        }
        return -(low + 1);  //key not found.
    }
 
同様にCollectionsにも同様の補助関数があるが,反復器を用いて特定の位置を取得する要素である.

public static 
    int binarySearch(List extends Comparable super T>> list, T key) {
        if (list instanceof RandomAccess || list.size()< BINARYSEARCH_THRESHOLD)
            return Collections. indexedBinarySearch(list, key);
        else
            return Collections. iteratorBinarySearch(list, key);
    }


private static 
    int indexedBinarySearch(List extends Comparable super T>> list, T key ) {
        int low = 0;
        int high = list.size()-1;

        while (low <= high) {
            int mid = ( low + high) >>> 1;
            Comparable super T> midVal = list.get( mid);
            int cmp = midVal.compareTo( key);

            if ( cmp < 0)
                low = mid + 1;
            else if ( cmp > 0)
                high = mid - 1;
            else
                return mid; // key found
        }
        return -(low + 1);  // key not found
    }

    private static 
    int iteratorBinarySearch(List extends Comparable super T>> list, T key )
    {
        int low = 0;
        int high = list.size()-1;
        ListIterator extends Comparable super T>> i = list.listIterator();

        while (low <= high) {
            int mid = ( low + high) >>> 1;
            Comparable super T> midVal = get(i , mid );
            int cmp = midVal.compareTo( key);

            if ( cmp < 0)
                low = mid + 1;
            else if ( cmp > 0)
                high = mid - 1;
            else
                return mid; // key found
        }
        return -(low + 1);  // key not found
    }

 /**
     * Gets the ith element from the given list by repositioning the specified
     * list listIterator.
     */
    private static  T get(ListIterator extends T> i, int index) {
        T obj = null;
        int pos = i.nextIndex();
        if (pos <= index) {
            do {
                obj = i.next();//    
            } while ( pos++ < index);
        } else {
            do {
                obj = i.previous();
            } while (-- pos > index);
        }
        return obj;
    }