 |
Das deutsche QBasic- und FreeBASIC-Forum
Für euch erreichbar unter qb-forum.de, fb-forum.de und freebasic-forum.de!
|
| Vorheriges Thema anzeigen :: Nächstes Thema anzeigen |
| Autor |
Nachricht |
Otacom
Anmeldungsdatum: 18.06.2006
Beiträge: 45
|
 Verfasst am: 19.09.2008, 13:19 Titel: Binary Search |
 |
|
| hi, an example of binary search in qbasic? thank.... |
|
| Nach oben |
|
 |
St_W
Anmeldungsdatum: 22.07.2007
Beiträge: 956
Wohnort: Austria
|
| Verfasst am: 19.09.2008, 22:50 Titel: |
|
|
hello,
I've read through the article on wikipedia about binary search and quickly coded the following program. There may be some bugs in it.
It does create an array with randomly generated numbers that are in ascending order. In that array you can search a specific number and the program returns the index, or -1 if the number wasn't found in the array.
I don't know if it's what you mean, but I hope so. Otherwise tell us(me).
| Code: |
' Coded by Stefan Wurzinger, 19th of September 2008
'
' All the code is released for free use and can be published and
' modified without my permissions
'
' I'm not responsible for any damages to your PC caused by this code
'
' Please excuse my bad english
DEFINT A-Z
DECLARE FUNCTION GetIndex% (IntArray%(), Number%)
RANDOMIZE TIMER
DIM IntArray(1 TO 100) AS INTEGER
'Fill Array with randomly increasing numbers
'The content of the Array has to be sorted
'from the lowest number to the highest, otherwise
'the binary search algorithm doesn't work.
w = INT(RND * 10)
FOR q = 1 TO 100
w = w + INT(RND * 20)
IntArray(q) = w
NEXT
'Print the array to screen
PRINT
COLOR 3
PRINT "Randomly generated array of 100 elements:"
COLOR 8
FOR q = 1 TO 100
PRINT IntArray(q); CHR$(7);
NEXT
COLOR 7
PRINT
PRINT
DO
INPUT "Search for which number (0 to abort)"; usrNumber
'If the entered Number is '0' then exit loop
IF usrNumber = 0 THEN EXIT DO
'Call the function "GetIndex" to get the index
'of the number in the array or -1 if the number
'wasn't found in the array
Index = GetIndex(IntArray(), usrNumber)
IF Index <> -1 THEN
COLOR 2
PRINT "Number "; IntArray(Index); " found on Index "; Index
COLOR 7
ELSE
COLOR 4
PRINT "Number "; usrNumber; " wasn't found in the array"
COLOR 7
END IF
LOOP
FUNCTION GetIndex% (IntArray(), Number)
Success = 0 'Number already found? (yes, if 1)
L = LBOUND(IntArray) 'Lower Bound of the Array
U = UBOUND(IntArray) 'Upper Bound of the Array
WHILE Success = 0 AND L <= U 'While Number not found
M = (L + U) \ 2 'Get the middle of Upper and Lower Bound
IF IntArray(M) = Number THEN 'If Number in the middle is accidentally...
Success = 1 'the searched Number set Success to true(1)
ELSE
IF Number < IntArray(M) THEN 'If Number is lower than the Number in the middle...
U = M - 1 'check the upper half of the array...
ELSE 'else...
L = M + 1 'check the lower half of the array
END IF
END IF
WEND 'loop
IF Success = 1 THEN 'If Number was found...
GetIndex% = M 'return Index of Number...
ELSE 'else...
GetIndex% = -1 'return -1 (could be changed to any value)
END IF
END FUNCTION
|
_________________
Aktuelle FreeBasic Builds, Projekte, Code-Snippets unter http://users.freebasic-portal.de/stw/
http://www.mv-lacken.at Musikverein Lacken (MV Lacken) |
|
| Nach oben |
|
|
Otacom
Anmeldungsdatum: 18.06.2006
Beiträge: 45
|
| Verfasst am: 20.09.2008, 16:44 Titel: |
|
|
good  , thank you  |
|
| Nach oben |
|
|
|
|
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.
|
|
FAQ
Suchen
Mitgliederliste
Benutzergruppen
Registrieren
Profil
Einloggen, um private Nachrichten zu lesen
Login
