private int findInsertionPoint ( Object o , int startIndex , int endIndex ) { int halfPt = ( ( endIndex - startIndex ) / 2 ) + startIndex ; int delta = compare ( get ( halfPt ) , o ) ; if ( delta < 0 ) { endIndex = halfPt ; } else if ( delta > 0 ) { startIndex = halfPt ; } else { // System.out.println("halfPt: " + halfPt); return halfPt ; } // the object in question falls between two elements if ( ( endIndex - startIndex ) <= 1 ) { // System.out.println("endIndex: " + endIndex); return endIndex + 1 ; } return findInsertionPoint ( o , startIndex , endIndex ) ; }
Conducts a binary search to find the index where Object o should be inserted .