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 Robert A. Rosenberg:
At 06:27 -0700 on 10/21/2013, retired mainframer 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).
