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:
- Find Midpoint: Calculate the index of the element in the exact middle of the current search range.
- Compare: Compare the value at the midpoint with the TARGET.
- 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.
- 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 ← LOW (start index)
LD DE, HIGH_BOUND_ADDR ; DE ← 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 ← 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 ← MID + 1
JP SEARCH_LOOP
NEW_RANGE_LOW:
; --- Target is LESS than MID. Discard HIGH half ---
CALL SET_HIGH_BOUND ; HIGH ← 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