# Oppolzer - Informatik / Blog

Blog-Hauptseite      Neuester Artikel      Älterer Artikel      Neuerer Artikel      Älterer gleiche Kategorie      Neuerer gleiche Kategorie

### ASSEMBLER-L - Binäre Suche mit ASSEMBLER (Codebeispiel)

 Subject: From: Bernd Oppolzer Reply-To: IBM Mainframe Assembler List Date: 2013.10.26 10:54:55

 ```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). > ```