private int findSlotBefore ( SearchKey searchKey ) { /* * int slot = 0; while (slot < contents.getNumRecords() && * getKey(contents, slot).compareTo(searchKey) < 0) slot++; return slot * - 1; */ // Optimization: Use binary search rather than sequential search int startSlot = 0 , endSlot = currentPage . getNumRecords ( ) - 1 ; int middleSlot = ( startSlot + endSlot ) / 2 ; if ( endSlot >= 0 ) { while ( middleSlot != startSlot ) { if ( getKey ( currentPage , middleSlot , keyType . length ( ) ) . compareTo ( searchKey ) < 0 ) startSlot = middleSlot ; else endSlot = middleSlot ; middleSlot = ( startSlot + endSlot ) / 2 ; } if ( getKey ( currentPage , endSlot , keyType . length ( ) ) . compareTo ( searchKey ) < 0 ) return endSlot ; else if ( getKey ( currentPage , startSlot , keyType . length ( ) ) . compareTo ( searchKey ) < 0 ) return startSlot ; else return startSlot - 1 ; } else return - 1 ; }
Calculates the slot right before the one having the specified search key .