Binary Search

By Adam Presley
0

Searching an array for some value is a common task. This code demonstrates how to use the binary search algorithm for this very purpose.

The binary search algorithm works by splitting a sorted array in halves and determining if the value you are searching for falls into the top or bottom half. It then splits THAT half in half, and keeps repeating this logic till it finds the index of the value in question. Overall the binary search is quite fast for sorted arrays.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

`---------------------------------------------------------
` PLEASE NOTE: The binary search relies on the array being
` sorted in ascending order.
`---------------------------------------------------------
dim GeneralArray(0) as string
 
`-------------------------------------
` Read the inline data into our array.
`-------------------------------------
restore __inline_data
 
repeat
	read temp$
 
	if temp$ <> ""
		array insert at bottom GeneralArray()
		Index = array count(GeneralArray()) - 1
 
		GeneralArray(Index) = temp$
	endif
until temp$ = ""
 
`----------------------------
` Show the data in the array.
`----------------------------
print "Here is the data in the array."
for index = 0 to (array count(GeneralArray()) - 1)
	print "INDEX " + str$(index) + ": " + GeneralArray(index)
next index
 
Name$ = "Roger DBCoder"
Index = BinaryStringSearch(array count(GeneralArray()), Name$)
 
if Index <> -1
	print : print "The index of the string '" + Name$ + "' is " + str$(Index)
else
	print : print "The index of the string '" + Name$ + "' could not be found."
endif
 
suspend for key
end
 
function BinaryStringSearch(Bottom, SearchString$)
	top = 0
	middle = 0
	found = 0
	returnvalue = -1
 
	while (found <> 1) and (Bottom >= top)
		middle = ((top + Bottom) / 2)
		if (middle = 0) and (Bottom = 1) then middle = 1
 
		if (SearchString$ = GeneralArray(middle))
			found = 1
		else
			if (asc(left$(GeneralArray(middle), 1))) < (asc(left$(SearchString$, 1)))
				top = middle + 1
			else
				Bottom = middle - 1
			endif
		endif
	endwhile
 
	if found = 1
		returnvalue = middle
	else
		returnvalue = -1
	endif
endfunction returnvalue
 
__inline_data:
data "Adam Presley", "Agent Smith", "Data DooDoo", "John Smith", "Roger DBCoder"