TheGameCreators - CodeBase - Binary String Search

Return to the CodeBase listing

Category: Miscellaneous

Version: 1.0

Information

Uploaded: 2nd Oct 2003 10:21

Modified: 1st Jan 1970 01:00

Author: TheOneRing

Summary

Search for a string in an array using the binary search.

Full Description

This example loads a set of strings into an array, then uses a binary search to find the index of a particular string. Please note that the binary search requires the array to be sorted in ascending order.

DarkBASIC Professional Source Code

` This code was downloaded from The Game Creators

` It is reproduced here with full permission

` http://www.thegamecreators.com

`---------------------------------------------------------

` 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

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"

Download

Please login to download

Comments

No comments yet.

Author Name:	TheOneRing
CodeBase Entries:	5

CodeBase - Binary String Search

Information

Summary

Full Description

DarkBASIC Professional Source Code

Download

Screen Shot

Author

Comments