=====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 [[http://www.bbcbasic.co.uk/bbcwin/manual/bbcwin9.html#binarychop|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:\\ \\ 
<code bb4w>
        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
</code>
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:\\ \\ 
<code bb4w>
        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
</code>
\\  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.