The Need for Fast Lookup

If you have a large list of data (e.g., all font character pointers, or a list of game variables) that is sorted alphabetically or numerically, checking every item sequentially (`memchr′ in Part 89) is inefficient. Binary Search is the solution: it finds the target by repeatedly dividing the search space in half.

The Principle: After each comparison, the algorithm eliminates half of the remaining elements. This makes the search time logarithmic, drastically speeding up large lookups.

The Binary Search Algorithm

To search for a target value (`TARGET′) in a sorted array:

  1. Find Midpoint: Calculate the index of the element in the exact middle of the current search range.
  2. Compare: Compare the value at the midpoint with the TARGET.
  3. Refine Range:
    • If MIDPOINT = TARGET: Success!
    • If MIDPOINT < TARGET: Discard the lower half; the new search range starts after the midpoint.
    • If MIDPOINT > TARGET: Discard the upper half; the new search range ends before the midpoint.
  4. Repeat: Loop back to Step 1 until the target is found or the search range is empty.

Z80 Implementation Focus

This routine requires careful management of three 16-bit pointers: LOW, HIGH, and MID (for the search boundaries).

Core Logic (Simplified):

BINARY_SEARCH:
    LD   HL, LOW_BOUND_ADDR   ; HL &larr; LOW (start index)
    LD   DE, HIGH_BOUND_ADDR  ; DE &larr; HIGH (end index)
    
SEARCH_LOOP:
    ; 1. Check if LOW > HIGH (Search range is empty)
    CALL CMP_HL_DE            ; Compare LOW (HL) vs HIGH (DE)
    JP   C, NOT_FOUND         ; If Carry=1, LOW > HIGH. Exit.

    ; 2. Calculate MID = (LOW + HIGH) / 2
    CALL CALCULATE_MIDPOINT   ; IX &larr; MID index

    ; 3. Compare TARGET with Value at MID (using 16-bit comparison, Part 87)
    CALL COMPARE_TARGET       ; Sets flags based on [MID] vs TARGET
    
    JP   Z, FOUND_IT          ; If Equal, success!
    JP   C, NEW_RANGE_LOW     ; If Carry=1, Target is less than MID.

    ; --- Target is GREATER than MID. Discard LOW half ---
    CALL SET_LOW_BOUND        ; LOW &larr; MID + 1
    JP   SEARCH_LOOP
    
NEW_RANGE_LOW:
    ; --- Target is LESS than MID. Discard HIGH half ---
    CALL SET_HIGH_BOUND       ; HIGH &larr; MID - 1
    JP   SEARCH_LOOP
    
NOT_FOUND:
    ; Return an error code (e.g., HL = FFFFH)
    RET
    
FOUND_IT:
    ; Return the address/index of the found item
    RET