BBC BASIC Programmers' Reference

User Tools

Site Tools

Trace: • memory_20usage_20monitor • storing_20structures_20containing_20strings
searching_20ordered_20lists

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Next revision		Previous revision
searching_20ordered_20lists [2018/03/31 13:19] – external edit 127.0.0.1searching_20ordered_20lists [2024/01/05 00:21] (current) – external edit 127.0.0.1
Line 2: Line 2:
  
 //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:\\ \\  //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$)         DEF FNwhere(A$(), S$)
         LOCAL B%, H%, T%         LOCAL B%, H%, T%
Line 13: Line 14:
         UNTIL H%=0         UNTIL H%=0
         IF S$=A$(B%) THEN = B% ELSE = -1         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:\\ \\  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$)         DEF FNwhere(A$(), S$)
         LOCAL B%, H%, R%, T%         LOCAL B%, H%, R%, T%
Line 28: Line 31:
         UNTIL H%=0         UNTIL H%=0
         IF S$=A$(B%) THEN = B% ELSE = -1         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. \\  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.
searching_20ordered_20lists.1522502379.txt.gz · Last modified: 2024/01/05 00:16 (external edit)