Problem Statement

A binary search divides a range of values into halves, and continues to narrow down the field of search until the unknown value is found. It is the classic example of a "divide and conquer" algorithm. As an analogy, consider the children's game "guess a number." The scorer has a secret number, and will only tell the player if their guessed number is higher than, lower than, or equal to the secret number. The player then uses this information to guess a new number. As the player, an optimal strategy for the general case is to start by choosing the range's midpoint as the guess, and then asking whether the guess was higher, lower, or equal to the secret number. If the guess was too high, one would select the point exactly between the range midpoint and the beginning of the range. If the original guess was too low, one would ask about the point exactly between the range midpoint and the end of the range. This process repeats until one has reached the secret number.

Given the starting point of a range, the ending point of a range, and the "secret value", implement a binary search through a sorted integer array for a certain number. Implementations can be recursive or iterative (both if you can). Print out whether or not the number was in the array afterwards. If it was, print the index also. There are several binary search algorithms commonly seen. They differ by how they treat multiple values equal to the given value, and whether they indicate whether the element was found or not. For completeness we will present pseudocode for all of them. All of the following code examples use an "inclusive" upper bound (i.e. high = N-1 initially). Any of the examples can be converted into an equivalent example using "exclusive" upper bound (i.e. high = N initially) by making the following simple changes (which simply increase high by 1): The algorithms are as follows (from Wikipedia). The algorithms return the index of some element that equals the given value (if there are multiple such elements, it returns some arbitrary one). It is also possible, when the element is not found, to return the "insertion point" for it (the index that the value would have if it were inserted into the array). Recursive Pseudocode: Iterative Pseudocode: The following algorithms return the leftmost place where the given element can be correctly inserted (and still maintain the sorted order). This is the lower (inclusive) bound of the range of elements that are equal to the given value (if any). Equivalently, this is the lowest index where the element is greater than or equal to the given value (since if it were any lower, it would violate the ordering), or 1 past the last index if such an element does not exist. This algorithm does not determine if the element is actually found. This algorithm only requires one comparison per level. Recursive Pseudocode: Iterative Pseudocode: The following algorithms return the rightmost place where the given element can be correctly inserted (and still maintain the sorted order). This is the upper (exclusive) bound of the range of elements that are equal to the given value (if any). Equivalently, this is the lowest index where the element is greater than the given value, or 1 past the last index if such an element does not exist. This algorithm does not determine if the element is actually found. This algorithm only requires one comparison per level. Note that these algorithms are almost exactly the same as the leftmost-insertion-point algorithms, except for how the inequality treats equal values. Recursive Pseudocode: Iterative Pseudocode: Make sure it does not have overflow bugs. The line in the pseudo-code above to calculate the mean of two integers: could produce the wrong result in some programming languages when used with a bounded integer type, if the addition causes an overflow. (This can occur if the array size is greater than half the maximum integer value.) If signed integers are used, and low + high overflows, it becomes a negative number, and dividing by 2 will still result in a negative number. Indexing an array with a negative number could produce an out-of-bounds exception, or other undefined behavior. If unsigned integers are used, an overflow will result in losing the largest bit, which will produce the wrong result. One way to fix it is to manually add half the range to the low number: Even though this is mathematically equivalent to the above, it is not susceptible to overflow. Another way for signed integers, possibly faster, is the following: where >>> is the logical right shift operator. The reason why this works is that, for signed integers, even though it overflows, when viewed as an unsigned number, the value is still the correct sum. To divide an unsigned number by 2, simply do a logical right shift.

Let's start with the solution:

*        Binary search             05/03/2017
BINSEAR  CSECT
         USING  BINSEAR,R13        base register
         B      72(R15)            skip savearea
         DC     17F'0'             savearea
         STM    R14,R12,12(R13)    save previous context
         ST     R13,4(R15)         link backward
         ST     R15,8(R13)         link forward
         LR     R13,R15            set addressability
         MVC    LOW,=H'1'          low=1
         MVC    HIGH,=AL2((XVAL-T)/2)  high=hbound(t)
         SR     R6,R6              i=0
         MVI    F,X'00'            f=false
         LH     R4,LOW             low
       DO WHILE=(CH,R4,LE,HIGH)    do while low<=high
         LA     R6,1(R6)             i=i+1
         LH     R1,LOW               low
         AH     R1,HIGH              +high
         SRA    R1,1                 /2  {by right shift}
         STH    R1,MID               mid=(low+high)/2
         SLA    R1,1                 *2
         LH     R7,T-2(R1)           y=t(mid)
       IF CH,R7,EQ,XVAL THEN         if xval=y then
         MVI    F,X'01'                f=true
         B      EXITDO                 leave
       ENDIF    ,                    endif
       IF CH,R7,GT,XVAL THEN         if y>xval then
         LH     R2,MID                 mid
         BCTR   R2,0                   -1
         STH    R2,HIGH                high=mid-1
       ELSE     ,                    else
         LH     R2,MID                 mid
         LA     R2,1(R2)               +1
         STH    R2,LOW                low=mid+1
       ENDIF    ,                    endif
         LH     R4,LOW               low
       ENDDO    ,                  enddo
EXITDO   EQU    *                exitdo:
         XDECO  R6,XDEC            edit i
         MVC    PG(4),XDEC+8       output i
         MVC    PG+4(6),=C' loops'
         XPRNT  PG,L'PG            print buffer
         LH     R1,XVAL            xval
         XDECO  R1,XDEC            edit xval
         MVC    PG(4),XDEC+8       output xval
       IF CLI,F,EQ,X'01' THEN      if f then
         MVC    PG+4(10),=C' found at '
         LH     R1,MID               mid
         XDECO  R1,XDEC              edit mid
         MVC    PG+14(4),XDEC+8      output mid
       ELSE     ,                  else
         MVC    PG+4(20),=C' is not in the list.'
       ENDIF    ,                  endif
         XPRNT  PG,L'PG            print buffer
         L      R13,4(0,R13)       restore previous savearea pointer
         LM     R14,R12,12(R13)    restore previous context
         XR     R15,R15            rc=0
         BR     R14                exit
T        DC     H'3',H'7',H'13',H'19',H'23',H'31',H'43',H'47'
         DC     H'61',H'73',H'83',H'89',H'103',H'109',H'113',H'131'
         DC     H'139',H'151',H'167',H'181',H'193',H'199',H'229',H'233'
         DC     H'241',H'271',H'283',H'293',H'313',H'317',H'337',H'349'
XVAL     DC     H'229'             <= search value
LOW      DS     H
HIGH     DS     H
MID      DS     H
F        DS     X                  flag
PG       DC     CL80' '            buffer
XDEC     DS     CL12               temp
         YREGS
         END    BINSEAR