private int binaryFindDelete ( int lower , int upper , Object delKey ) { java . util . Comparator comp = insertComparator ( ) ; int xcc ; /* Current compare result */ int i ; int idx = - 1 ; /* Returned index (-1 if not found) */ while ( lower <= upper ) /* Until they cross */ { i = ( lower + upper ) >>> 1 ; /* Mid-point of current range */ xcc = comp . compare ( delKey , _nodeKey [ i ] ) ; if ( xcc < 0 ) /* SEARCH_KEY < NODE_KEY */ upper = i - 1 ; /* Discard upper half of range */ else /* SEARCH_KEY >= NODE_KEY */ { if ( xcc > 0 ) /* SEARCH_KEY > NODE_KEY */ lower = i + 1 ; /* Discard lower half of range */ else /* SEARCH_KEY FOUND */ { idx = i ; /* Remember the index */ break ; /* We're done */ } } } return idx ; }
Use binary search to find the delete key .