Challenge: Binary Search.

[relsoft]

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

[Sterling Christensen]

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

Yeah, any binary search algorithm requires a sorted list.

[Moneo]

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.
*****

[Moneo]

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

*****