Binary Search Method

[SMcNeill]

A simple demostration of how to implement and use a binary search method:

Code: QB64: [Select]

1. SCREEN _NEWIMAGE(800, 600, 32)
2.  
3. OPEN "466544 Word List.txt" FOR BINARY AS #1
4. DIM SHARED WordList(1 TO 466544) AS STRING
5. DO UNTIL EOF(1)
6.     count = count + 1
7.     LINE INPUT #1, WordList(count)
8. LOOP
9.  
10.  
11.  
12. DO
13.     _KEYCLEAR
14.     INPUT "Give me any word"; search$
15.     search$ = LTRIM$(RTRIM$(search$))
16.     PRINT "Searching for "; search$
17.     IF search$ = "" THEN END
18.     index = FindIndex(search$)
19.     IF index THEN
20.         PRINT "Word was found at position "; index; " in "; SearchTimes; "passes."
21.     ELSE
22.         PRINT "Word was not in list."
23.         PRINT "Previous word was ==> "; WordList(LastIndex - 1)
24.         PRINT "Next word was ======> "; WordList(LastIndex + 1)
25.         PRINT "Search took"; SearchTimes; "passes."
26.     END IF
27.     PRINT
28. LOOP
29.  
30.  
31.  
32. FUNCTION FindIndex (search$)
33.     SHARED SearchTimes, LastIndex
34.     SearchTimes = 0
35.     min = 1 'lbound(wordlist)
36.     max = 370099 'ubound(wordlist)
37.     DO UNTIL found
38.         SearchTimes = SearchTimes + 1
39.         gap = (min + max) \ 2
40.         compare = _STRICMP(search$, WordList(gap))
41.         IF compare > 0 THEN
42.             min = gap + 1
43.         ELSEIF compare < 0 THEN
44.             max = gap - 1
45.         ELSE
46.             FindIndex = gap
47.             found = -1
48.         END IF
49.         IF max - min <= 1 THEN LastIndex = gap: found = -1 'it's not in the list
50.         PRINT min, max, search$, WordList(gap), compare
51.         SLEEP
52.     LOOP
53. END FUNCTION
54.  

The word list has 466544 words in it, so it takes a few seconds to load into memory.  Searching for a word in the list however, and finding its index, is almost instantaneous.  At *MOST*, this will make 19 passes to either find, or eliminate a word from the list.

Now, let's apply the same list to STx's hash tables as written here: https://www.qb64.org/forum/index.php?topic=1001.msg101972#msg101972

Code: QB64: [Select]

1. DIM SHARED HashTableSize AS LONG
2. HashTableSize = 300007 ' Best to use a big prime number. Bigger examples are 611953 and 1014729.
3.  
4.  
5. DIM Counter(300007) 'So we can count how deep some of the tables go
6.  
7. PRINT "Loading dictionary..."
8.  
9. OPEN "466544 Word List.txt" FOR BINARY AS #1
10. DO WHILE NOT EOF(1)
11.     LINE INPUT #1, a$
12.     d = HashFunc(a$) ' Calculate the hash value (array address) of the word on hand.
13.     Counter(d) = Counter(d) + 1
14. LOOP
15. CLOSE #1
16.  
17. FOR i = 1 TO 300007
18.     IF Counter(i) > max THEN max = Counter(i)
19. NEXT
20.  
21. PRINT "Lists go up to "; max; " levels deep."
22.  
23.  
24. PRINT "Done."
25.  
26. END
27.  
28.  
29.  
30. FUNCTION HashFunc (a AS STRING) ' input string
31.     DIM sum AS DOUBLE
32.     sum = HashTableSize
33.     FOR k = 1 TO LEN(a)
34.         sum = sum + k * COS(ASC(MID$(a, k, 1))) ' Without the linear factor of k, permutations have same hash values.
35.     NEXT
36.     sum = ABS(VAL(ReplaceSubString$(STR$(sum), ".", "")))
37.     sum = sum MOD HashTableSize
38.     HashFunc = sum
39. END FUNCTION
40.  
41. FUNCTION ReplaceSubString$ (a AS STRING, b AS STRING, c AS STRING)
42.     j = INSTR(a, b)
43.     IF j > 0 THEN
44.         r$ = LEFT$(a, j - 1) + c + ReplaceSubString$(RIGHT$(a, LEN(a) - j + 1 - LEN(b)), b, c)
45.     ELSE
46.         r$ = a
47.     END IF
48.     ReplaceSubString$ = r$
49. END FUNCTION

Notice that the hash table has entries which go up to 10 levels deep in it, so we first need to hash to the proper address and then check the list for up to 10 different entries before finding the right one.

19 loops MAX in this case for the Binary Search Method, verses 11 (hash + 10 levels) MAX for the Hash Table...

... so it seems as if the Hash Table wins in this case. (Also depending on how efficient the method is for looking up the 10 levels deep info is; some commands have more overhead than others.)

BUT...

Hash Tables require your data in memory PLUS the table itself being in memory. 

All the Binary Search Method requires is for the data to be memory (and sorted).  (And if memory constraints are a true issue, it works quite well directly with Random Access Files, as you can simply use the index number to reference them with GET #1, index, word$.)


Either way, it seems to be a nice improvement over Pete's old method which he talks about here: https://www.qb64.org/forum/index.php?topic=1001.msg101983#msg101983

And, as for Stx's question:

17 steps? 18 steps? Where did these numbers come from? How do I interpret them in O(n) notation?

That was covered here: https://www.qb64.org/forum/index.php?topic=1001.msg101981#msg101981

A max of N searches, where 2^N > Index.  ;)

2^18 = 262,144
INDEX = 466544 words
2^19 = 524,288

So our max number of searches is 2^N > Index... Or 19 in this case. 

I think the burden's on you to do the speed test m8 (for a large data set with lots of performance demand).

I think the above offers a fairly decent comparison of the two methods.  Feel free to run them and actually time them in various performance tests if you want. 

One large advantage to the binary search is lesser memory usage and simplicity to implement.

A large advantage to hash tables is the fact that your data doesn't need to be sorted to search properly.

Both seem equally useful to me, and neither should be completely dismissed out-of-hand.  ;)

NOTE: Feel free to remove (or comment out) the following statements, if you want, in the code above.  It's mainly there just to help highlight the search process.

Code: QB64: [Select]

1.         PRINT min, max, search$, WordList(gap), compare
2.         SLEEP

[STxAxTIC]

Nice and honest writeup.

An actual speed test will be to rattle off say 50,000 consecutive lookups. To say it "feels instaneous" for one word at a time is a bit pedestrian. Let's talk Pete into making the test.

EDIT: Just looked up the average conversion time for binary sort is O(log n). That solves the speed question. On binary sort's best day you have O(n), which is incidentally what you get on hash's worst day.

You're right about the memory argument. Good thing it's no longer 1973 and we have been cramming gigabytes into keychains since 2002. Hashing is safe, memory-wise.  (Speed is still coveted though.)

[SMcNeill]

Code: QB64: [Select]

1. SCREEN _NEWIMAGE(800, 600, 32)
2.  
3. OPEN "466544 Word List.txt" FOR BINARY AS #1
4. DIM SHARED WordList(1 TO 466544) AS STRING
5. DO UNTIL EOF(1)
6.     count = count + 1
7.     LINE INPUT #1, WordList(count)
8. LOOP
9.  
10. DIM RandomWords(50000) AS STRING
11. FOR i = 1 TO 50000
12.     c = INT(RND * 466544) + 1
13.     RandomWords(i) = WordList(c)
14. NEXT
15.  
16. t# = TIMER
17. FOR i = 1 TO 50000
18.     index = FindIndex(RandomWords(i))
19. NEXT
20. PRINT USING "###.### seconds lookup"; TIMER - t#
21.  
22. END
23.  
24.  
25.  
26.  
27. DO
28.     _KEYCLEAR
29.     INPUT "Give me any word"; search$
30.     search$ = LTRIM$(RTRIM$(search$))
31.     PRINT "Searching for "; search$
32.     IF search$ = "" THEN END
33.     index = FindIndex(search$)
34.     IF index THEN
35.         PRINT "Word was found at position "; index; " in "; SearchTimes; "passes."
36.     ELSE
37.         PRINT "Word was not in list."
38.         PRINT "Previous word was ==> "; WordList(LastIndex - 1)
39.         PRINT "Next word was ======> "; WordList(LastIndex + 1)
40.         PRINT "Search took"; SearchTimes; "passes."
41.     END IF
42.     PRINT
43. LOOP
44.  
45.  
46.  
47. FUNCTION FindIndex (search$)
48.     SHARED SearchTimes, LastIndex
49.     SearchTimes = 0
50.     min = 1 'lbound(wordlist)
51.     max = 370099 'ubound(wordlist)
52.     DO UNTIL found
53.         SearchTimes = SearchTimes + 1
54.         gap = (min + max) \ 2
55.         compare = _STRICMP(search$, WordList(gap))
56.         IF compare > 0 THEN
57.             min = gap + 1
58.         ELSEIF compare < 0 THEN
59.             max = gap - 1
60.         ELSE
61.             FindIndex = gap
62.             found = -1
63.         END IF
64.         IF max - min <= 1 THEN LastIndex = gap: found = -1 'it's not in the list
65.         ' PRINT min, max, search$, WordList(gap), compare
66.         ' SLEEP
67.     LOOP
68. END FUNCTION

0.055 seconds on my PC to find 50,000 random words.  Personally, I’d call that “almost instantaneous”, but what do I know?  My naming sense sucks.  LOL

Now you just need to speed test your method to lookup the same 50,000 words.  (Which is why theres no RANDOMIZER TIMER in there.)

[Pete]

Hey I'm still over in the other thread with my new method that makes you guys look like losers! Sorry, I gave brain cells today at the Head Cross clinic and for a few hours after that procedure, I find myself channeling Ted.

Pete

[SMcNeill]

Nevermind.  It’s not worth the effort.  Use it or not; there it is.

[Pete]

Not alphabetizing a file for a binary search would be as stupid as not using the Dewey Decimal system for stacking books. The books in here somewhere, just start doing a shelf by shelf search. So I don't think we should be considering that as part of this discussion. This is about an organized word list vs a hash table, which alphabetizing in the hash method is of absolutely no consequence.

In my 25 year old example, the speed was adequate because I organized the data and sub-divided the list into different alphabetized folders. If I had to loop through 50,000 random words in a single list with the slower INPUT AS method, I'd still be waiting to see if I spelled dumb-ass correctly.

Pete

[STxAxTIC]

Steve, the big-O notation is designed to specifically not compare apples to oranges. Dicscrete calculus will be a lesson for another time... I just cant right now, my facepalm hurts.

[SMcNeill]

Use it or not; there it is.

I’d still love to see a similar speed test for your method.  I’m curious how big a difference it could be.

[STxAxTIC]

It's open source. Have a ball. (Might wanna optimize it first.)

[Pete]

Steve, the big-O notation is designed to specifically not compare apples to oranges. Dicscrete calculus will be a lesson for another time... I just cant right now, my facepalm hurts.

Dicscrete calculus, Bill? I think you'd better chose a search method and get that spell checker up and working for craps sake.

If you mean discrete calculus, is that one of those math courses offered at night for active singles? If so, what is the probably of completing the course without contracting a nasty case of standard deviations?

Pete :D

[STxAxTIC]

Haha, not sure who promised I was making a spell checker. The dictionizer thing I posted is still a working product... or... prototype. I consider the whole case closed pretty much.

[bplus]

Steve there is a bug in your FindIndex function:

Code: QB64: [Select]

1. SCREEN _NEWIMAGE(800, 600, 32)
2.  
3. OPEN "466544 Word List.txt" FOR BINARY AS #1
4. DIM SHARED WordList(1 TO 466544) AS STRING
5. DO UNTIL EOF(1)
6.     count = count + 1
7.     LINE INPUT #1, WordList(count)
8. LOOP
9. CLOSE #1
10. DIM RandomWords(50000) AS STRING
11. FOR i = 1 TO 50000
12.     c = INT(RND * 466544) + 1
13.     RandomWords(i) = WordList(c)
14. NEXT
15. PRINT "Steve's 50000 word lookup with binary search"
16. t# = TIMER
17. FOR i = 1 TO 10
18.     index = FindIndex(RandomWords(i))
19.     IF index THEN PRINT WordList(index) ELSE PRINT RandomWords(i) + " not found!"
20. NEXT
21. PRINT USING "###.### seconds lookup"; TIMER - t#
22.  
23.  
24. 'pete's method
25. OPEN "466544 Word List.txt" FOR BINARY AS #1
26. word$ = SPACE$(LOF(1))
27. GET #1, , word$
28. CLOSE #1
29. PRINT "Pete's 50000 word lookup using INSTR to get position in string of word."
30. t# = TIMER
31. FOR i = 1 TO 10
32.     place = INSTR(word$, RandomWords(i) + CHR$(13) + CHR$(10))
33.     PRINT MID$(word$, place, LEN(RandomWords(i)))
34. NEXT
35. PRINT USING "####.### seconds lookup"; TIMER - t#
36.  
37. END
38.  
39.  
40.  
41.  
42. DO
43.     _KEYCLEAR
44.     INPUT "Give me any word"; search$
45.     search$ = LTRIM$(RTRIM$(search$))
46.     PRINT "Searching for "; search$
47.     IF search$ = "" THEN END
48.     index = FindIndex(search$)
49.     IF index THEN
50.         PRINT "Word was found at position "; index; " in "; SearchTimes; "passes."
51.     ELSE
52.         PRINT "Word was not in list."
53.         PRINT "Previous word was ==> "; WordList(LastIndex - 1)
54.         PRINT "Next word was ======> "; WordList(LastIndex + 1)
55.         PRINT "Search took"; SearchTimes; "passes."
56.     END IF
57.     PRINT
58. LOOP
59.  
60.  
61.  
62. FUNCTION FindIndex (search$)
63.     SHARED SearchTimes, LastIndex
64.     SearchTimes = 0
65.     min = 1 'lbound(wordlist)
66.     max = 370099 'ubound(wordlist)
67.     DO UNTIL found
68.         SearchTimes = SearchTimes + 1
69.         gap = (min + max) \ 2
70.         compare = _STRICMP(search$, WordList(gap))
71.         IF compare > 0 THEN
72.             min = gap + 1
73.         ELSEIF compare < 0 THEN
74.             max = gap - 1
75.         ELSE
76.             FindIndex = gap
77.             found = -1
78.         END IF
79.         IF max - min <= 1 THEN LastIndex = gap: found = -1 'it's not in the list
80.         ' PRINT min, max, search$, WordList(gap), compare
81.         ' SLEEP
82.     LOOP
83. END FUNCTION
84.  
85.  

[SMcNeill]

A couple of little things was working against the original running as intended:

Code: QB64: [Select]

1. SCREEN _NEWIMAGE(800, 600, 32)
2.  
3. OPEN "466544 Word List.txt" FOR BINARY AS #1
4. DIM SHARED WordList(466545) AS STRING
5. PRINT "Loading library"
6. DO UNTIL EOF(1)
7.     count = count + 1
8.     LINE INPUT #1, WordList(count)
9. LOOP
10. CLOSE #1
11.  
12. PRINT "Sorting"
13. Sort WordList()
14.  
15. PRINT "Looking up"
16. DIM RandomWords(50000) AS STRING
17. FOR i = 1 TO 50000
18.     c = INT(RND * 466544) + 1
19.     RandomWords(i) = WordList(c)
20. NEXT
21. PRINT "Steve's 50000 word lookup with binary search"
22. t# = TIMER
23. FOR i = 1 TO 10
24.     index = FindIndex(RandomWords(i))
25.     PRINT "Searching for: "; RandomWords(i),
26.     IF index THEN PRINT WordList(index) ELSE PRINT "NOT FOUND!"
27. NEXT
28. PRINT USING "###.### seconds lookup"; TIMER - t#
29.  
30.  
31. 'pete's method
32.  
33. 'FOR i = 1 TO 466545
34. '    adding brackets to words to stop a false match, such as "dog" being found in "dogfood"
35. '    word$ = word$ + "{" + WordList(i) + "}" 'build up the search list
36. '    IF i < 50001 THEN RandomWords(i) = "{" + RandomWords(i) + "}"
37. 'NEXT
38.  
39. OPEN "466544 Word List.txt" FOR BINARY AS #1
40. word$ = SPACE$(LOF(1))
41. GET #1, , word$
42. CLOSE #1
43.  
44.  
45.  
46. PRINT "Pete's 50000 word lookup using INSTR to get position in string of word."
47. t# = TIMER
48. FOR i = 1 TO 10
49.     place = INSTR(word$, RandomWords(i) + CHR$(13) + CHR$(10))
50.     PRINT "Searching for: "; RandomWords(i),
51.     IF place THEN PRINT MID$(word$, place, LEN(RandomWords(i))) ELSE PRINT "NOT FOUND!"
52. NEXT
53. PRINT USING "####.### seconds lookup"; TIMER - t#
54.  
55. END
56.  
57.  
58.  
59.  
60. DO
61.     _KEYCLEAR
62.     INPUT "Give me any word"; search$
63.     search$ = LTRIM$(RTRIM$(search$))
64.     PRINT "Searching for "; search$
65.     IF search$ = "" THEN END
66.     index = FindIndex(search$)
67.     IF index THEN
68.         PRINT WordList(index); " was found at position "; index; " in "; SearchTimes; "passes."
69.     ELSE
70.         PRINT "Word was not in list."
71.         PRINT "Previous word was ==> "; WordList(LastIndex - 1)
72.         PRINT "Next word was ======> "; WordList(LastIndex + 1)
73.         PRINT "Search took"; SearchTimes; "passes."
74.     END IF
75.     PRINT
76. LOOP
77.  
78.  
79.  
80. FUNCTION FindIndex (search$)
81.     SHARED SearchTimes, LastIndex
82.     SearchTimes = 0
83.     min = 1 'lbound(wordlist)
84.     max = 466544 'ubound(wordlist)
85.  
86.     DO UNTIL found
87.         SearchTimes = SearchTimes + 1
88.         gap = (max + min) \ 2
89.         'IF gap = oldgap THEN gap = gap + 1
90.         compare = _STRCMP(search$, WordList(gap))
91.         IF compare > 0 THEN
92.             oldmin = min
93.             min = gap
94.         ELSEIF compare < 0 THEN
95.             oldmax = max
96.             max = gap
97.         ELSE
98.             FindIndex = gap
99.             found = -1
100.             EXIT FUNCTION
101.         END IF
102.         oldgap = gap
103.         IF max - min < 1 THEN LastIndex = gap: found = -1 'it's not in the list
104.         ' PRINT min, max, search$, WordList(gap), compare
105.         ' SLEEP
106.     LOOP
107. END FUNCTION
108.  
109. SUB Sort (Array() AS STRING)
110.     'The dice sorting routine, optimized to use _MEM and a comb sort algorithm.
111.     'It's more than fast enough for our needs here I th ink.  ;)
112.     gap = UBOUND(array)
113.     DO
114.         gap = 10 * gap \ 13
115.         IF gap < 1 THEN gap = 1
116.         i = 0
117.         swapped = 0
118.         DO
119.             IF _STRCMP(Array(i), Array(i + gap)) > 0 THEN
120.                 SWAP Array(i), Array(i + gap)
121.                 swapped = -1
122.             END IF
123.             i = i + 1
124.         LOOP UNTIL i + gap > UBOUND(Array)
125.     LOOP UNTIL swapped = 0 AND gap = 1
126. END SUB
127.  

First issue:  The data in the wordlist isn't fully alphabetical...  O_o!!   It needed a quick sort so we can search it properly.  Just look at the first few lines; it should've been obvious, but I overlooked it:

2
1080
&c
10-point
10th
11-point
12-point
16-point
18-point
1st

Since when does "2" come before "1"??

Sorting routine added, and bug was squashed.


Glitch 2:

OPEN "466544 Word List.txt" FOR BINARY AS #1
max = 370099 'ubound(wordlist)

There's a small difference in those two numbers...  (I'd originally was using a smaller file, before I found this one on the web and grabbed it for the larger data set.)

There's no way we could find a ton of words in the list, while only checking about 3/4 of them...

Glitch fixed.


Glitch #3:

        ELSE
            FindIndex = gap
            found = -1
        END IF
        IF max - min <= 1 THEN LastIndex = gap: found = -1 'it's not in the list

We're missing one important piece of program flow here: 

        ELSE
            FindIndex = gap
            found = -1
            EXIT FUNCTION
        END IF
        IF max - min < 1 THEN LastIndex = gap: found = -1 'it's not in the list

We'd find the proper result, and then if the gap was small enough between the last numbers, we'd lie and claim it wasn't actually in the list...

Glitch fixed.


All should be working as advertised now, in the code above.  ;)

Sidenote:  Your implementation of Pete's method is glitched.  "dog" would be found if "dogfood" was included in the list, while "dog" actually wasn't.

I was going to do a fix for the issue, but you'd need to take a nap while it was running:

Code: QB64: [Select]

1. FOR i = 1 TO 466545 ' adding brackets to words to stop a false match, such as "dog" being found in "dogfood"
2.     word$ = word$ + "{" + WordList(i) + "}" 'build up the search list
3.     IF i < 50001 THEN RandomWords(i) = "{" + RandomWords(i) + "}"
4. NEXT

I tried to rebuild the already loaded and sorted list with brackets delimiting the words, but I didn't have the patience to sit and listen to my PC try to sound like an airplane with all the fans going full throttle for who knows how long....

[luke]

And just because we can, here's a recursive binary sort:

Code: QB64: [Select]

1. DEFLNG A-Z
2.  
3. OPEN "words" FOR INPUT AS #1
4. DIM SHARED WordList(99170) AS STRING
5. DO UNTIL EOF(1)
6.     LINE INPUT #1, WordList(count)
7.     count = count + 1
8. LOOP
9.  
10. DO
11.     INPUT "> ", search$
12.     IF search$ = "" THEN END
13.     index = find(search$, 0, UBOUND(wordlist))
14.     IF index >= 0 THEN
15.         PRINT "Found "; WordList(index); " at"; index
16.     ELSE
17.         PRINT "Not found"
18.     END IF
19. LOOP
20.  
21. FUNCTION find (word$, start, finish)
22.     size = finish - start + 1
23.     mid = size \ 2
24.     cmp = _STRCMP(WordList(start + mid), word$)
25.     SELECT CASE cmp
26.         CASE 0
27.             find = start + mid
28.         CASE IS > 0
29.             IF size = 1 THEN find = -1 ELSE find = find(word$, start, start + mid - 1)
30.         CASE IS < 0
31.             IF size = 1 THEN find = -1 ELSE find = find(word$, start + mid + 1, finish)
32.     END SELECT
33. END FUNCTION

(My word list had all the words beginning with a capital letter listed first, so I'm using _STRCMP)

[SMcNeill]

Use it or not; there it is.

I’d still love to see a similar speed test for your method.  I’m curious how big a difference it could be.

It's open source. Have a ball. (Might wanna optimize it first.)

So, since Stx wasn't willing to do a speed comparison, I did:

Code: QB64: [Select]

1. DIM SHARED HashTableSize AS LONG
2. HashTableSize = 300007 ' Best to use a big prime number. Bigger examples are 611953 and 1014729.
3.  
4. DIM SHARED LB AS STRING ' Make sure that bcracketing sequences do not appear in the data source, otherwise use (a) special character(s).
5. DIM SHARED RB AS STRING
6. LB = "{"
7. RB = "}"
8.  
9. DIM SHARED EnglishDictionary(HashTableSize) AS STRING ' Hash table size does not need to equal the size of the source dictionary itself.
10.  
11. OPEN "466544 Word List.txt" FOR BINARY AS #1
12.  
13. DIM SHARED WordList(466545) AS STRING
14. PRINT "Loading library"
15. DO UNTIL EOF(1)
16.     count = count + 1
17.     LINE INPUT #1, WordList(count)
18. LOOP
19. CLOSE #1
20.  
21. Sort WordList()
22.  
23. i = 0
24. FOR i = 1 TO 466545
25.     b$ = WordList(i) 'the word to store
26.     c$ = LTRIM$(RTRIM$(STR$(i))) 'to store the index
27.     d = HashFunc(b$) ' Calculate the hash value (array address) of the word on hand.
28.     EnglishDictionary(d) = EnglishDictionary(d) + LB + b$ + RB + LB + c$ + RB
29. NEXT
30. CLOSE #1
31. PRINT "Done creating Hash Table."
32.  
33. ' Done developing fast lookup tool. Now time for an application.
34.  
35. PRINT "Looking up"
36. DIM RandomWords(50000) AS STRING
37. FOR i = 1 TO 50000
38.     c = INT(RND * 466544) + 1
39.     RandomWords(i) = WordList(c)
40. NEXT
41.  
42. t# = TIMER
43. FOR i = 1 TO 50000
44.     'PRINT "Searching for: "; RandomWords(i),
45.     l$ = Lookup$(RandomWords(i))
46.     IF l$ <> "" THEN
47.         l = INSTR(l$, " ")
48.         word$ = LEFT$(l$, l - 1)
49.         index = VAL(MID$(l$, l + 1))
50.         'PRINT WordList(index) 'to show that we got the index back successfully
51.         'ELSE
52.         'PRINT "NOT FOUND!"
53.     END IF
54. NEXT
55. PRINT USING "###.### seconds lookup using Hash Table"; TIMER - t#
56.  
57. t# = TIMER
58. FOR i = 1 TO 50000
59.     index = FindIndex(RandomWords(i))
60.     'PRINT "Searching for: "; RandomWords(i),
61.     'IF index THEN 'to show that we got the index back successfully
62.     '    PRINT WordList(index)
63.     'ELSE
64.     '    PRINT "NOT FOUND!"
65.     'END IF
66. NEXT
67. PRINT USING "###.### seconds lookup using Binary Search"; TIMER - t#
68.  
69. PRINT
70. PRINT "And just to compare results -- the first 15 words:"
71. FOR i = 1 TO 10
72.     'PRINT "Searching for: "; RandomWords(i),
73.     l$ = Lookup$(RandomWords(i))
74.     IF l$ <> "" THEN
75.         l = INSTR(l$, " ")
76.         word$ = LEFT$(l$, l - 1)
77.         index = VAL(MID$(l$, l + 1))
78.         PRINT WordList(index), 'to show that we got the index back successfully
79.     ELSE
80.         PRINT "NOT FOUND!",
81.     END IF
82.     index = FindIndex(RandomWords(i))
83.     'PRINT "Searching for: "; RandomWords(i),
84.     IF index THEN 'to show that we got the index back successfully
85.         PRINT WordList(index)
86.     ELSE
87.         PRINT "NOT FOUND!"
88.     END IF
89. NEXT
90.  
91.  
92.  
93.  
94. FUNCTION Lookup$ (a AS STRING)
95.     r$ = ""
96.     b$ = EnglishDictionary(HashFunc(a))
97.     c$ = ""
98.     d$ = ""
99.     IF b$ <> "" THEN
100.         DO WHILE c$ <> a
101.             c$ = ReturnBetween(b$, LB, RB)
102.             IF c$ = "" THEN EXIT DO
103.             b$ = RIGHT$(b$, LEN(b$) - LEN(LB + c$ + RB))
104.             d$ = ReturnBetween(b$, LB, RB)
105.         LOOP
106.     END IF
107.     r$ = a + "  " + d$
108.     Lookup$ = r$
109. END FUNCTION
110.  
111. FUNCTION ReturnBetween$ (a AS STRING, b AS STRING, c AS STRING) ' input string, left bracket, right bracket
112.     i = INSTR(a, b)
113.     j = INSTR(a, c)
114.     f = LEN(c)
115.     ReturnBetween$ = MID$(a, i + f, j - (i + f))
116. END FUNCTION
117.  
118. FUNCTION HashFunc (a AS STRING) ' input string
119.     DIM sum AS DOUBLE
120.     sum = HashTableSize
121.     FOR k = 1 TO LEN(a)
122.         sum = sum + k * COS(ASC(MID$(a, k, 1))) ' Without the linear factor of k, permutations have same hash values.
123.     NEXT
124.     sum = ABS(VAL(ReplaceSubString$(STR$(sum), ".", "")))
125.     sum = sum MOD HashTableSize
126.     HashFunc = sum
127. END FUNCTION
128.  
129. FUNCTION ReplaceSubString$ (a AS STRING, b AS STRING, c AS STRING)
130.     j = INSTR(a, b)
131.     IF j > 0 THEN
132.         r$ = LEFT$(a, j - 1) + c + ReplaceSubString$(RIGHT$(a, LEN(a) - j + 1 - LEN(b)), b, c)
133.     ELSE
134.         r$ = a
135.     END IF
136.     ReplaceSubString$ = r$
137. END FUNCTION
138.  
139.  
140. SUB Sort (Array() AS STRING)
141.     'The dice sorting routine, optimized to use _MEM and a comb sort algorithm.
142.     'It's more than fast enough for our needs here I th ink.  ;)
143.     gap = UBOUND(array)
144.     DO
145.         gap = 10 * gap \ 13
146.         IF gap < 1 THEN gap = 1
147.         i = 0
148.         swapped = 0
149.         DO
150.             IF _STRCMP(Array(i), Array(i + gap)) > 0 THEN
151.                 SWAP Array(i), Array(i + gap)
152.                 swapped = -1
153.             END IF
154.             i = i + 1
155.         LOOP UNTIL i + gap > UBOUND(Array)
156.     LOOP UNTIL swapped = 0 AND gap = 1
157. END SUB
158.  
159. FUNCTION FindIndex (search$)
160.     SHARED SearchTimes, LastIndex
161.     SearchTimes = 0
162.     min = 1 'lbound(wordlist)
163.     max = 466544 'ubound(wordlist)
164.  
165.     DO UNTIL found
166.         SearchTimes = SearchTimes + 1
167.         gap = (max + min) \ 2
168.         compare = _STRCMP(search$, WordList(gap))
169.         IF compare > 0 THEN
170.             min = gap
171.         ELSEIF compare < 0 THEN
172.             max = gap
173.         ELSE
174.             FindIndex = gap
175.             found = -1
176.             EXIT FUNCTION
177.         END IF
178.         IF max - min < 1 THEN LastIndex = gap: found = -1 'it's not in the list
179.         ' PRINT min, max, search$, WordList(gap), compare
180.         ' SLEEP
181.     LOOP
182. END FUNCTION
183.  
184.  

In both search instances, we use the same word list, the same 50,000 word search list, and we return both the word we're searching for and its index position in the list.

Now, I imagine that Stx will come along and tell me I'm doing something wrong with the routine he provided, but the screenshot below is the results I get.  If there's something wrong with things, I'm more than happy to learn from whatever the issue is: