searching_20ordered_20lists

*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

Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Share Alike 4.0 International