Searching ordered lists
by Richard Russell, December 2006
The fastest way to search an ordered list is the binary search; you can find a description of how it works in the main BB4W documentation. The code below is a slightly simplified version, which searches an alphabetically-ordered string array for an exact match to a supplied string:
DEF FNwhere(A$(), S$) LOCAL B%, H%, T% T% = DIM(A$(),1) H% = 2 WHILE H%<T% H% *= 2:ENDWHILE H% /= 2 REPEAT IF (B%+H%)<=T% IF S$>=A$(B%+H%) B% += H% H% /= 2 UNTIL H%=0 IF S$=A$(B%) THEN = B% ELSE = -1
If the supplied string matches one of the elements in the array the function returns the index of the matching element. If there is no match the function returns -1.
Note that the entire array must be pre-sorted into alphabetical sequence.
Important note:
It is important that the method you use to sort the array is compatible with the method you use to search the array, i.e. that they use the same collation order. Specifically, if you use the above FNwhere function you can sort the array using version 1.3 (or later) of the SORTLIB library and set the second parameter of FN_sortinit() to 2.
If you use an earlier version of SORTLIB, or set the parameter to a different value, then the comparisons you make when searching the string should also use the CompareString function:
DEF FNwhere(A$(), S$) LOCAL B%, H%, R%, T% T% = DIM(A$(),1) H% = 2 WHILE H%<T% H% *= 2:ENDWHILE H% /= 2 REPEAT IF (B%+H%)<=T% THEN SYS "CompareString", &400, 0, S$, LEN(S$), A$(B%+H%), LEN(A$(B%+H%)) TO R% IF R%<>1 B% += H% ENDIF H% /= 2 UNTIL H%=0 IF S$=A$(B%) THEN = B% ELSE = -1
By changing the second parameter of CompareString from 0 to 1 a case insensitive comparison is made. That would be appropriate if you specified the ignore case option when using SORTLIB.