User Tools

Site Tools


searching_20ordered_20lists

Differences

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

Link to this comparison view

searching_20ordered_20lists [2018/03/31 13:19]
127.0.0.1 external edit
searching_20ordered_20lists [2018/04/17 18:36] (current)
tbest3112 Added syntax highlighting
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.txt ยท Last modified: 2018/04/17 18:36 by tbest3112