TheGameCreators - CodeBase - Binary search of an array

Return to the CodeBase listing

Category: Miscellaneous

Version: 1.0

Information

Uploaded: 18th Jan 2007 20:03

Modified: 1st Jan 1970 01:00

Author: IanM

Summary

Binary search of an array for exact or nearest match

Full Description

This code will allow you to search through a sorted array in the fastest possible manner.<br /> <br /> The example code using a simple string array and inserts data into the array to ensure that the array stays sorted.

DarkBASIC Professional Source Code

` This code was downloaded from The Game Creators

` It is reproduced here with full permission

` http://www.thegamecreators.com

dim SearchArray(20) as string

` Prepare an initial array - don't need to do this, an empty array works fine too

for i=0 to 20

SearchArray(i) = chr$(i + 65)

next i

repeat

` Read a new string

read InsertString$

if InsertString$ <> ""

` Find the insert position

Position = BinarySearch( InsertString$, 1 )

` If it's past the end of the array, append

if Position > array count( SearchArray() )

array insert at bottom SearchArray()

else

` Otherwise, insert

array insert at element SearchArray(), Position

endif

` Set the new item

SearchArray(Position) = InsertString$

endif

until InsertString$ = ""

` Display the array contents

for i=0 to array count( SearchArray() )

print i, " - ", SearchArray(i)

wait key

end

` Some data to insert

data "@ Insert at the front"

data "Z Insert at the end"

data "G Somewhere in the middle"

data "  Insert at the front again"

data "H"

data "I"

data ""

function BinarySearch(Target as string, Nearest as integer)

local High as integer

local Low as integer

local Middle as integer

` Set the Low and High points outside of the array

Low = -1

High = array count( SearchArray() )+1

` Loop while the difference between them is above 1 (ie, they have not passed or matching)

while High - Low > 1

` Pick a nid-point

Middle = (High + Low) / 2

` Test to see if the item is below the target value

if SearchArray(Middle) < Target

` If it is, move the low point to the mid-point

Low = Middle

else

` Otherwise, move the high point to the mid-point

High = Middle

endif

endwhile

` If not looking for a best match, then need to do some further checking

if Nearest = 0

` If the high-point is still beyond the end of the array, exit with a 'not found'

if High > array count( SearchArray() ) then exitfunction -1

` If the item currently pointed to by the high-point is not the one, exit with a 'not found'

if SearchArray(High) <> Target then exitfunction -1

` At this point, we have an exact match

endif

endfunction High

Download

Please login to download

Comments

No comments yet.

Author Name:	IanM
CodeBase Entries:	26

CodeBase - Binary search of an array

Information

Summary

Full Description

DarkBASIC Professional Source Code

Download

Screen Shot

Author

Comments