private void binaryFindIndex ( int lower , int upper , Object new1 , NodeInsertPoint point ) { java . util . Comparator comp = insertComparator ( ) ; int xcc ; /* Current compare result */ int lxcc = + 1 ; /* Remembered compare result */ int i ; int idx = upper + 1 ; /* Found index plus one */ while ( lower <= upper ) /* Until they cross */ { i = ( lower + upper ) >>> 1 ; /* Mid-point of current range */ xcc = comp . compare ( new1 , _nodeKey [ i ] ) ; if ( ! ( xcc > 0 ) ) /* SEARCH_KEY <= NODE_KEY */ { upper = i - 1 ; /* Discard upper half of range */ idx = i ; /* Remember last upper bound */ lxcc = xcc ; /* Remember last upper compare result */ } else /* SEARCH_KEY >= NODE_KEY */ lower = i + 1 ; /* Discard lower half of range */ } if ( lxcc != 0 ) /* Never had an equal compare */ point . setInsertPoint ( idx - 1 ) ; /* Desired point is previous one */ else /* Had an equal compare */ point . markDuplicate ( idx ) ; /* Key is a duplicate at point "idx" */ }
Use binary search to find the insert point .