protected int findTransition ( int state , char c ) { int start = d_stateOffsets . get ( state ) ; int end = transitionsUpperBound ( state ) - 1 ; // Binary search while ( end >= start ) { int mid = start + ( ( end - start ) / 2 ) ; if ( d_transitionChars [ mid ] > c ) end = mid - 1 ; else if ( d_transitionChars [ mid ] < c ) start = mid + 1 ; else return mid ; } return - 1 ; }
Find the transition for the given character in the given state . Since the transitions are ordered by character we can use a binary search .