home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 18 REXX / 18-REXX.zip / bsrch.rex < prev    next >
OS/2 REXX Batch file  |  1996-01-17  |  5KB  |  124 lines
  1. /* rexx */
  2.  
  3. /*  Bsearch -  
  4.  A binary search is useful when there is a large amount of data
  5.  to search through very quickly. It is comparable to the way a human
  6.  would look up a word in a dictionary or phone book. You could start
  7.  at the beginning and read sequentially until the word or number is found,
  8.  and that's fine if the name or word is near the beginning, but most often
  9.  you would start in the middle of the phone book. Here is a table:
  10.  
  11.       Search:  A_Test B_Test C_Test D_Test E_Test 
  12.      1 A_Test <- 3
  13.      2 B_Test <- 2     <-2 
  14.      3 C_Test <- 1     <-1    <-1    <-1    <-1     <- Start in the middle
  15.      4 D_Test                        <-2    <-2
  16.      5 E_Test                               <-3
  17.       Passes:    3       2      1      2      3
  18.  
  19. An array of 5 elements can be searched in 3 passes max. The stem is cut in 
  20. half for every pass. This is almost always much faster then sequentially 
  21. reading through each stem. The main drawback to this approach is that all 
  22. data in the stem  MUST be sorted. (Just like a dictionary or Phone book)
  23.  
  24. This implementation of Bsearch returns a space delimited string of information 
  25. "Found Where Passes"
  26.  
  27. The search is case sensitive. But it would be easy to modify.
  28.  
  29. This routine was written for regina running on a Linux system, but I see no
  30. reason why it wouldn't run under OS/2 as well.
  31.  
  32. It is based on Ethan Winer's book: QuickBasic Techniques and Utilities
  33. Binary Search routine. But is modified for rexx.
  34.  
  35. It is important to note that the stem to search must be exposed to the 
  36. routine, and that since rexx has no "bound checking" a common convention
  37. is to use stem.0 for the number of elements. Bsearch uses this as the
  38. default, but a range may be specified in args 3,4.
  39.  
  40.   Result = Bsearch("Animal.","Cat",2,10) /* look for a Cat */
  41.  
  42. Will look at the stem "Animal." for the word "Cat". The range it will
  43. look at is animal.2 to animal.10
  44.  
  45. if the range is not specified, and animal.0 contains a NON numeric string,
  46. bsearch will bomb. Of course, Animal. must have been sorted. 
  47. */
  48.  
  49. /* the following is test code */
  50. Gl.0 = 26
  51. /* produce a SORTED test stem of 26 */
  52. DO I = 1 to Gl.0
  53.   Gl.I = D2C(I+64)||"_Test"
  54. END
  55. TestFind = "A_Test Zebra B_Test M_Test N_Test Y_Test Z_Test Apple"
  56. DO I = 1 to WORDS(TestFind)
  57.   Find = WORD(TestFind,I)
  58.   Say "Looking for : '"Find"'"
  59.   Result = Bsearch("Gl.",Find)   /* look for find */
  60.   Found = Word(Result,1)         /* Did we find it? 0/1 */
  61.   Where = Word(Result,2)         /* where was it? */
  62.   Passes = Word(Result,3)        /* how long did it take? */
  63.   IF Found THEN
  64.     Say "'"Find"' Was found element: "Where" it took "Passes" Passes."
  65.   ELSE
  66.     Say "'"Find"' Was not found, closest: "Where" it took "Passes" Passes."
  67.  
  68.   Say "Value of Gl."Where" : '"Gl.Where"'"          
  69. END
  70. Call Charout ,"Do you wish to look for every element [N] "
  71. Pull Q
  72. Say
  73. if Q = "Y" Then DO
  74. Say "Finding every element"
  75.   Do I = 1 to 26
  76.     Find = Gl.I
  77.     Result = Bsearch("Gl.",Find)
  78.     IF WORD(Result,1) THEN
  79.       Say "Found: '"Find"' element "WORD(Result,2)" Passes: "Word(Result,3)
  80.     ELSE
  81.       Say "'"Find"' was not found, bsearch is broken, do not use"
  82.   END
  83. END
  84. Exit
  85.  
  86. /* this is the actual routine, cut & paste to your program. */          
  87. /*************************************************************************** 
  88.  * Binary search a stem. Stem MUST be sorted 
  89.  * Stem = Arg(1)  - Stem to look at
  90.  * Find = Arg(2)  - What to look for
  91.  * From = Arg(3)  - Where to start (default 1)
  92.  * To   = Arg(4)  - Where to stop  (default Stem.0)
  93.  * 
  94.  * Returns a string:
  95.  * Found Where Passes
  96.  * Found - 0/1 Did we find it?
  97.  * Where - Where in the stem did we find it?
  98.  * Passes - How many passes (Remove this for speed, just for demonstration)
  99.  * 
  100.  * This routine was ported from a QuickBasic Function by Ethan Winer
  101.  * in his book "Basic Techniques an Utilities" ISBN 1-56276-008-4
  102.  ***************************************************************************/
  103. Bsearch: procedure expose Gl.
  104. stem = ARG(1)
  105. Find = ARG(2)
  106. IF DATATYPE(ARG(3),"N") THEN ; Min = Arg(3) ; Else ; Min = 1
  107. IF DATATYPE(ARG(4),"N") THEN ; Max = Arg(4) ; Else ; Max = VALUE(Stem"0")
  108. Pass = 0                 /* remove if you want */
  109. DO FOREVER 
  110.   Pass = Pass + 1        /* remove if you want */
  111.   Try = (Max + Min) % 2  /* start in middle */
  112.   Now = VALUE(Stem||Try)
  113.   IF Now = Find THEN
  114.      return "1 "Try" "Pass /* remove the "pass" if you want */
  115.  
  116.   IF Now > Find THEN    /* this cuts the range in 1/2   */
  117.      Max = (Try - 1)
  118.   Else
  119.      Min = (Try + 1)
  120.  
  121.   IF Max < Min THEN
  122.      return "0 "Try" "Pass    /* remove "pass" if you want */
  123. END
  124.