Qbasicnews.com
September 18, 2019, 08:23:34 AM *
Welcome, Guest. Please login or register.

Login with username, password and session length
News: Back to Qbasicnews.com | QB Online Help | FAQ | Chat | All Basic Code | QB Knowledge Base
 
   Home   Help Search Login Register  
Pages: [1]
  Print  
Author Topic: Challenge: Binary Search.  (Read 5672 times)
Moneo
Na_th_an
*****
Posts: 1971


« on: July 09, 2003, 08:14:35 PM »

BINARY SEARCH:

1) Declare your definition of what a binary search is.

2) Define a table with 10 sorted entries (elements) which your program will do the search on.

3) Write and post the code to do a binary search on the above table, searching for a user provided argument, and issuing a found or not found message at the end.
*****
Logged
whitetiger0990
__/--\__
*****
Posts: 2964



WWW
« Reply #1 on: July 09, 2003, 09:31:20 PM »

Huh?
Logged


[size=10]Back by popular demand!
I will byte and nibble you bit by bit until nothing remains but crumbs.[/size]
Ninkazu
Been there, done that
*****
Posts: 1169



WWW
« Reply #2 on: July 09, 2003, 10:16:40 PM »

a binary search goes through an array by first taking its size divided by 2, then only asking if the number is higher or lower than the number at the current entry. After knowing if it's higher or lower, it halves itself in the according direction.

I couldn't figure out how to code this (I'm stupid) and I'm not sure how accurate my description is.
Logged

am an asshole. Get used to it.
na_th_an
*/-\*
*****
Posts: 8244



WWW
« Reply #3 on: July 10, 2003, 12:16:33 AM »

Code:
DECLARE FUNCTION binarySearchRec% (Array%(), i1%, i2%, n%)
DECLARE FUNCTION binarySearch% (Array%(), n%)

' Binary search example by Na Than

CLS : RANDOMIZE TIMER

' First make a sorted array

DIM Array%(15)

PRINT "POSTN:"
PRINT "CONT:"

FOR i% = 0 TO 15
   Array%(i%) = a%
   LOCATE 1, 8 + i% * 3: PRINT i%
   LOCATE 2, 8 + i% * 3: PRINT a%
   a% = a% + INT(RND * 5)
NEXT i%

PRINT

' Test loop. Enter sumthin <0 to exit
DO
   PRINT "Find what";
   INPUT n%
   IF n% < 0 THEN EXIT DO

   Res% = binarySearch%(Array%(), n%)

   IF Res% <> -1 THEN
      PRINT "Found at "; Res%
   ELSE
      PRINT "Not Found"
   END IF
LOOP

'
' This function searches for n% in Array%() returning its position,
' or "-1" if n% is not in Array%().
'
FUNCTION binarySearch% (Array%(), n%)
   binarySearch% = binarySearchRec%(Array%(), LBOUND(Array%), UBOUND(Array%), n%)
END FUNCTION

'
' binarySearchRec% is called by binarySearch% takes four parameters:
'
' Array%() -> The array to look inside of.
' i1% -> lower limit.
' i2% -> upper limit.
' n% -> Number that is searched.
'
' We basicly take the array, and look the element in the mid place.
' if it equals n%, we have found it!
'
' If the element in the array is SMALLER than n%, we should look in
' the right half of the array, so we call ourselves recursively with
' new i1%, i2% values.
'
' If the element in the array is BIGGER than n%, we should look in the
' left half of the array.
'
' This (of course) only works if the array is sorted.
'
FUNCTION binarySearchRec% (Array%(), i1%, i2%, n%)
   Res% = -1
   IF i1% > i2% THEN binarySearchRec% = Res%: EXIT FUNCTION
   midPoint% = i1% + (i2% - i1%) \ 2
   IF Array%(midPoint%) = n% THEN
      Res% = midPoint%
   ELSEIF Array%(midPoint%) < n% THEN
      Res% = binarySearchRec%(Array%(), midPoint% + 1, i2%, n%)
   ELSE
      Res% = binarySearchRec%(Array%(), i1%, midPoint% - 1, n%)
   END IF
   binarySearchRec% = Res%
END FUNCTION
Logged

SCUMM (the band) on Myspace!
ComputerEmuzone Games Studio
underBASIC, homegrown musicians
[img]http://www.ojodepez-fanzine.net/almacen/yoghourtslover.png[/i
relsoft
*/-\*
*****
Posts: 3927



WWW
« Reply #4 on: July 10, 2003, 02:16:32 AM »

Can anyone point to a DL of Address.bas? It has a binary search algo in there. ;*)

*curses CT....
Logged

y smiley is 24 bit.


Genso's Junkyard:
http://rel.betterwebber.com/
Moneo
Na_th_an
*****
Posts: 1971


« Reply #5 on: July 10, 2003, 02:11:57 PM »

WHITETIGER:
---------------
See Ninkazu's definition which is pretty good.
An example of a binary search that you may have seen is:
You ask a person to think of a number from 1 to 100. You can find his number in 7 questions. Why? Because 2 to the 7th power is 128 which is greater than 100.  Each of your questions is going to eliminate half of the possibiities. You start your questions at the mid-point of 50. You first ask if the answer is less than 50. If yes, your next question will be against 25. If no, your next question will be against 75, and so on.

NINKAZU:
-----------
I think you have the idea. Why don't you try it.

NATHAN:
----------
I certainly did not expect a recursive solution. I honestly don't think recursion is required for this. It only takes about 16 lines of code to do it straightforward. I have not checked it out yet because the PC that I'm using right now doesn't have my compiler. Later.
*****
Logged
Moneo
Na_th_an
*****
Posts: 1971


« Reply #6 on: July 10, 2003, 09:54:13 PM »

NATHAN,

Wonderful! Your program works vey well --- a very complete solution. It never would have occurred to me to use recursion. You should post this program in Antoni's recursion challenge. It's a very strong candidate to be the winner.
*****
Logged
na_th_an
*/-\*
*****
Posts: 8244



WWW
« Reply #7 on: July 11, 2003, 12:27:52 AM »

Thanks man. In fact, I did it very naturally. Sometimes, the recursive sollution is the easy one for me, as I tend to think recursively in most cases.

And, sinceramente, no se me ocurre cómo hacerlo de forma iterativa Tongue
Logged

SCUMM (the band) on Myspace!
ComputerEmuzone Games Studio
underBASIC, homegrown musicians
[img]http://www.ojodepez-fanzine.net/almacen/yoghourtslover.png[/i
Moneo
Na_th_an
*****
Posts: 1971


« Reply #8 on: July 11, 2003, 12:46:24 AM »

Nathan,
Don't forget to post this under Antoni's topic.
*****
Logged
Sterling Christensen
Na_th_an
*****
Posts: 1328


« Reply #9 on: July 11, 2003, 01:15:02 AM »

A binary search checks the middle item of those that have not yet been eliminated, and (depending on whether the item is too high or too low) eliminates either the top half or the bottom half from consideration. It does this over and over until it has either found the item or exhausted all possibilites.

Code:

DECLARE FUNCTION binarySearch% (item%, first%, last%, array%(), where%)

DEFINT A-Z

'---------------------------------------
' Define a random sorted array:
RANDOMIZE TIMER
DIM array(1 TO 10)
n = 0
FOR i = 1 TO 10
   n = n + INT(RND * 100)
   array(i) = n
NEXT i
'---------------------------------------

'---------------------------------------
' Display the elements of the array:
CLS
PRINT
PRINT "Items in the array:"
FOR i = 1 TO 10
   PRINT array(i);
NEXT i
PRINT
'---------------------------------------

'---------------------------------------
' Ask the user for an item to search for:
PRINT
INPUT "Item to search for: ", item
PRINT
'---------------------------------------

'---------------------------------------
' Attempt to find it, then display the result:
IF binarySearch(item, 1, 10, array(), position) THEN
   PRINT item; "was found at position"; position
ELSE
   PRINT item; "was not found in the list."
END IF
'---------------------------------------

END

'
' Returns false if the item isn't found, or true if it was in which
'   case where% is the item's index.
'
FUNCTION binarySearch (item, first, last, array(), where)

DO WHILE first <= last
 
  middle = (first + last) \ 2
  i = array(middle)

  IF i = item THEN binarySearch = -1: where = middle: EXIT FUNCTION
 
  IF i < item THEN first = middle + 1 ELSE last = middle - 1

LOOP

binarySearch = 0

END FUNCTION
Logged
relsoft
*/-\*
*****
Posts: 3927



WWW
« Reply #10 on: July 11, 2003, 03:28:32 AM »

Only problem I see is you have to have a soted list. Wink But that's just me. ;*)
Logged

y smiley is 24 bit.


Genso's Junkyard:
http://rel.betterwebber.com/
Sterling Christensen
Na_th_an
*****
Posts: 1328


« Reply #11 on: July 11, 2003, 04:29:46 AM »

Quote from: "relsoft"
Only problem I see is you have to have a soted list. Wink But that's just me. ;*)


Yeah, any binary search algorithm requires a sorted list.
Logged
Moneo
Na_th_an
*****
Posts: 1971


« Reply #12 on: July 11, 2003, 01:56:04 PM »

STERLING C,
---------------
Very nice, straightforward job. It works fine. I even modified it for only 1 table element, and it also works.

RELSOFT,
-----------
You're right, the list must be sorted. When the binary search function doesn't know where the list comes from, that is who made it, it would be adviseable for the function to do a quick sequence check on the list up front. If it's out-of-sequence, you should abort the program with a fatal error.

TO ALL,
--------
When you write this kind of general purpose routine for sorting or searching a table, you have to take into consideration that the routine may be given an empty table (null) or one with only 1 table element in it.
*****
Logged
Moneo
Na_th_an
*****
Posts: 1971


« Reply #13 on: August 18, 2003, 09:11:05 PM »

I guess it's time I posted my old code for doing a binary search.
Code:
REM "BINSER" BINARY SEARCH SUBROUTINE. Edward F. Moneo 02-Jun-89.
REM
REM  CALLING SEQUENCE:
REM         BSTAB() = Name of the table to be searched.
REM               Z = Number of entries in table.
REM           BSARG = Search argument.
REM
REM  ON OUTPUT:   Z = Found table index, (Z=0=Not found)

BINSER:
  IF Z=0 THEN RETURN
  ZTOP=0                      'Pointer to the top -1
  ZBOT=Z+1                  'Pointer to the bottom+1
  IF Z=1 THEN               'Set increment (table offset)
     ZINC=1                    
  ELSE
     ZINC=Z/2
  END IF

  DO
      Z=ZTOP+ZINC
      IF BSTAB(Z)=BSARG THEN RETURN
      IF BSTAB(Z) < BSARG THEN
         ZTOP=ZTOP+ZINC
      ELSE
         ZBOT=ZTOP+ZINC
      END IF
      ZINC=ZINC/2
      IF ZINC=0 THEN ZINC=1
  LOOP WHILE ZTOP+ZINC < ZBOT

  Z=0
 RETURN

*****
Logged
Pages: [1]
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.21 | SMF © 2015, Simple Machines Valid XHTML 1.0! Valid CSS!