Oppolzer - Informatik / Blog

This is not necessary, and the binary search code is not at all complicated.

Look at this:

          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


R3 - points at the start of the sorted table at the beginning
R4 - index, starting from 1, of the lower limit of the range to be examined
R5 - upper limit, is initialized with EINGANZ at the beginning
R6 - is used to compute the index "in the middle"
R7 - is used to compute the address of the element "in the middle"

then the element in the middle is compared against SUCHARG,
depending on the result, R4 and R5 are adjusted, and the LOOP is
executed again, if necessary.

if not, you have a result (found or not).

R9 is used to count the loop executions, which will be floor(log2(n)),
where n is the number of elements in the vector (in the worst case).

At our shop, we have a macro which does this. No need to code
the binary search yourself every time you need it.

Kind regards

Bernd



Am 21.10.2013 22:49, schrieb R.R.:
> At 06:27 -0700 on 10/21/2013, R.M. wrote about Re:
> Linear search vs binary:
>
>> If your search target is uniformly distributed against the key, then on
>> average a linear search will require 1750 iterations of your compare
>> loop.
>> A binary search will require a constant 12 iterations regardless of
>> distribution.
>
> One trick that would make the binary search code simpler is to make
> the table 4096 entries long not 3500 long. Place 298 low value
> entries, then the 3500 live entries, and then 298 high values. This
> will cause some wasted compares when you hit the padding low/high
> values but you do not need to worry about how to spit the table in
> half for each round (the size is always the prior power of 2).
>