User Tools

Site Tools


searching_20ordered_20lists

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.

This website uses cookies for visitor traffic analysis. By using the website, you agree with storing the cookies on your computer.More information
searching_20ordered_20lists.txt · Last modified: 2018/04/17 18:36 by tbest3112