Oppolzer - Informatik / Blog

I just would like to add that the program that I posted some days ago can be
used to do non matching searches as well. In the not-found case the loop is left
with R6 containing the index (and R7 the address) of the element that matches
best (the element that has been compared in the last execution of the loop and
has found not to be equal to the search argument), and it is left to the caller
to take appropriate action after examining the found resp. not found return
code. The binary search logic itself stays the same and is no more complicated.

To make it easier to follow this, I post the code once again:


          MVI   GEFUNDEN,C'0'
          LH    R4,=H'1'
          L     R5,EINGANZ
*
          XR    R9,R9 DURCHLAUFZAEHLER = 0
*
          LOOP WHILE,((R4),<=,(R5))
          AHI   R9,1
*                               MITTE DER RESTL. ELEMENTE ERMITTELN
          LA    R6,0(R4,R5)                R5+R4->R6 (ANZ. ELEMENTE)
          SRA   R6,1                       DURCH 2 DIVIDIEREN
          LR    R7,R6
          BCTR  R7,0
          MH    R7,=Y(L'ESATZ)
          AR    R7,R3                      TATSAECHL. ADR. MITTE
          IF   (SUCHARG,<,3(R7)),*,(SUCHARG,>,3(R7))
*
          THEN
          LR    R5,R6                      GROESSER, WEITERSUCHEN
          BCTR  R5,0
*
          THEN
          LA    R4,1(R6)                   KLEINER, WEITERSUCHEN
*
          ELSE
          MVI   GEFUNDEN,C'1'
          BREAK
*
          EIF
          ELOOP


For some explanations regarding the SP macros used (and other topics) see
earlier in this thread.

Kind regards

Bernd


Am Montag, 28. Oktober 2013 13:20 schrieben Sie:
> There is one respect in which this thread on binary search has been
> unsatisfactory.  It has concerned itself only with match-seeking
> binary search, and bounds-seeking binary search is at  least as
> useful.
>
> A greatest lower bound (GLB) on a search argument or a least upper
> bound (LUB) on it came be searched for in the same tables in which
> matches are sought.
>