'===========================================================================
' Subject: BINARY SEARCH                     Date: 02-06-97 (00:50)       
' Author:  Brian Mclaughlin                  Code: ASM                    
' Origin:  comp.lang.basic.misc            Packet: ASMCODE.ABC
'===========================================================================
; BSEARCH.ASM - assemble with MASM 5.1 or compatible assembler
;             - for QB4.x / PDS only
;             - written by Brian McLaughlin. Released to public domain.
;
; This FUNCTION accepts an integer value to search for in a sorted array,
; along with the address of the first element and the total number of
; elements in the array. It returns the number of the element where the
; value was found (assuming a 1-based array). If the value is not found,
; it returns the element (as a negative number) where the value would be 
; inserted into the array to preserve its sorted order.  
;
; For example: given a search value of 105, if element 10 contains 100 and 
; element 11 contained 110, BSearch would return -11.
;
; BSearch will give valid results ONLY for an array of integers, that is
; sorted in ascending order (lowest to highest), and has no duplicate
; values.
;
; DECLARE FUNCTION BSearch% (FindValue%, SEG Array%, TotalElements%)
;
; Example:
;         LookFor% = 666   'see if any elements of TestArray%() = 666
;         FirstElem% = LBOUND(TestArray%)
;         TotalElem% = UBOUND(TestArray%) - FirstElem% + 1
;         Result% = BSearch%(LookFor%, TestArray%(FirstElem%), TotalElem%)
;
;         IF Result% > 0 THEN
;           Result% = Result% + FirstElem% - 1
;           PRINT "Found "; LookFor%; " in element "; Result%
;         END IF

.MODEL MEDIUM, BASIC
.CODE
    Last DW 0

BSearch PROC USES SI DI, Value:WORD, Array:DWORD, Elems:WORD
    Mov BX, Value      ; point BX at Value
    Mov AX, [BX]       ; AX = value to be searched for
    Mov BX, Elems      ; point BX at Elems
    Mov DX, [BX]       ; DX = total number of elements
    Inc DX             ; adding one allows last element to be searched
    Mov DI, DX         ; DI = last element in search area
    Xor SI, SI         ; SI = first element in search area
    Mov Last, DX       ; Last = most recent element searched
    Lds CX, Array      ; point DS:CX at first element of array
    Cmp DX, 3          ; see if Elems was 0 or 1 (DX was inc'ed)
    Jb  ZeroOrOne      ; if so, deal with it as a special case
Search:
    Mov BX, DI         ; DI = top element of "search area"
    Add BX, SI         ; BX points to element halfway between top/bottom
    Add BX, CX         ; add offset of first element within DS
    And BL, 0FEh       ; this is needed whenever DI = SI+1
    Mov DX, [BX]       ; DX = the value at current "halfway" element
    Sub BX, CX         ; readjust BX "back" by amount of offset in CX
    Shr BX, 1          ; and then adjust from offset to index value
    Cmp BX, Last       ; was this element searched once before?
    Je  NotFound       ; if so, we've run out of search area
    Cmp DX, AX         ; does this element match Value?
    Je  Found          ; if it does, we've found our element!
    Mov Last, BX       ; remember we looked here already
    Cmp DX, AX         ; now compare again
    Jg  TopDown        ; if DX was > value, adjust top down
    Mov SI, BX         ; otherwise adjust bottom up
    Jmp SHORT Search   ; and keep on looking
TopDown:
    Mov DI, BX         ; adjust the top down
    Jmp SHORT Search   ; and continue looking

NotFound:
    Or  BX, BX         ; find out if BX = 0
    Jz  BXZero         ; if so, we must go decide what that means
    Neg BX             ; return a negative number
    Sub BX, 2          ; adjust 0-based to 1-based and el below to el above
    Jmp SHORT Exit
Found:
    Inc BX             ; adjust 0-based to 1-based return value
Exit:
    Mov AX, BX         ; put return value into AX
    Push SS
    Pop DS
    Ret

ZeroOrOne:
    Mov BX, -1         ; assume a return value of -1
    Dec DX             ; readjust DX to value in Elems
    Or  DX, DX         ; see if Elems = 0
    Jz  Exit           ; if so, exit with return value of -1
    Mov SI, CX         ; points DS:SI at first (and only) element
    Mov CX, [SI]       ; CX = value of only element
    Cmp AX, CX         ; how does it compare to search value?
    Jl  Exit           ; if it's below, exit with -1
    Dec BX             ; assume a return value of -2
    Cmp AX, CX         ; compare again
    Jg  Exit           ; exit with -2
    Mov BX, 1          ; or else, search value equals first element
    Jmp SHORT Exit     ; so return with 1
BXZero:
    Dec BX             ; search value is <> first element, assume it's <
    Cmp DX, AX         ; now, see which it is
    Jg  Exit           ; if it's "<" return -1
    Dec BX             ; otherwise value is ">" so,
    Jmp SHORT Exit     ; return -2
BSearch ENDP
    END