# Binary search

[Courses](https://asm-editor.specy.app/learn/courses.md) › [Z80 assembly](https://asm-editor.specy.app/learn/courses/z80.md) › Examples

Web page: https://asm-editor.specy.app/learn/courses/z80/examples/binary-search

> Search twelve ascending unsigned bytes by halving a half-open range; e receives the index or 0xFF, while the middle index is saved on the stack for address calculation.

The same program in: [M68K](https://asm-editor.specy.app/learn/courses/m68k/examples/binary-search.md), [MIPS](https://asm-editor.specy.app/learn/courses/mips/examples/binary-search.md), [RISC-V](https://asm-editor.specy.app/learn/courses/risc-v/examples/binary-search.md), [x86-64](https://asm-editor.specy.app/learn/courses/x86/examples/binary-search.md)

A binary search looks for an unsigned byte in an ascending array. Instead of checking every byte,
it probes the middle of the part that could still contain the target. This program searches the
twelve bytes below for `91`. It leaves the matching index in `e`; if no byte matches, it leaves
`FF` in `e`.

Open the program in the editor, choose **Build**, then use **Step** for the first two probes or
choose **Run** to finish it. The register panel shows hexadecimal values. With the supplied target,
`e` ends as `09`; `d` still holds `5B`, so `de` is `5B09`. Open the memory panel at `9000` to see
the array.

```z80
count equ 12

    .org 0x8000
    ld d, 91            ; the value we are looking for
    ld b, 0             ; low = 0
    ld c, count         ; high = count, one past the last element
    ld e, 0xFF          ; found = -1, meaning not there
search:
    ld a, b
    cp c
    jr nc, search_done  ; while(low < high)
    add a, c            ; low + high
    srl a               ; mid = (low + high) / 2
    push af             ; mid, kept while a is used for the element
    ld hl, numbers
    add a, l
    ld l, a
    jr nc, addressed
    inc h               ; the carry into the high byte
addressed:
    ld a, (hl)          ; numbers[mid]
    cp d                ; numbers[mid] - target
    jr z, hit
    jr c, go_right      ; it was too small, look above it
    pop af              ; mid back
    ld c, a             ; high = mid
    jr search
go_right:
    pop af
    inc a
    ld b, a             ; low = mid + 1
    jr search
hit:
    pop af
    ld e, a             ; found = mid
search_done:
    halt

    .org 0x9000
numbers: .db 2, 5, 8, 12, 16, 23, 38, 56, 72, 91, 100, 127
```

The live range is **half-open**: `[low, high)`. `low` is included and `high` is one past the last
possible index, so the initial range is `[0, 12)`. That makes the three outcomes after a probe
direct:

| Comparison of `numbers[mid]` with the target | Next range          |
| -------------------------------------------- | ------------------- |
| Too small                                    | `low = mid + 1`     |
| Too large                                    | `high = mid`        |
| Equal                                        | return `mid` in `e` |

`cp d` subtracts the target from the probed byte without keeping the result. C is set when that
byte is smaller, so `jr c, go_right` takes the first case. A larger byte falls through to
`high = mid`. The loop stops when `low` catches `high`: `[9, 9)`, for example, contains no index.

For the supplied search for `91`, the two probes are:

| `low` | `high` | `mid` | Probed byte | Result |
| ---: | ---: | ---: | --- |
| 0 | 12 | 6 | 38 | too small; `low = 7` |
| 7 | 12 | 9 | 91 | match; `e = 09` |

Change `ld d, 91` to `ld d, 90`, build, and run again. The complete no-match path is short:

| `low` | `high` | `mid` | Probed byte | Result |
| ---: | ---: | ---: | --- |
| 0 | 12 | 6 | 38 | too small; `low = 7` |
| 7 | 12 | 9 | 91 | too large; `high = 9` |
| 7 | 9 | 8 | 72 | too small; `low = 9` |

Now `low` and `high` are both 9, so the loop ends without reaching `hit`. `e` was initialized to
`FF` and was never changed, making `de` `5AFF`. `FF` is safe as the not-found marker here because
the valid indices are only `00` through `0B`.

`srl a` divides the sum by two, rounding down, to make the middle index. This exact program uses a
one-byte count and indices, and it forms `low + high` in the one-byte register `a`; keep `count` at
128 or less so that sum cannot overflow. The twelve-byte demo is well inside that limit. Its inputs
must be ascending unsigned bytes, and `d` is an unsigned byte target. `de` is simply two adjacent
registers here: target in `d`, result in `e`.

The address calculation starts with `hl = numbers` and adds the index to its low byte. If that
addition carries, `inc h` completes the pointer addition. In this listing `numbers` is visibly at
`9000`, but the carry-handling code also stays correct if the array is moved near the end of a page.

Finally, `a` needs to hold both the middle index and the byte read from memory. `push af` saves the
index before the read, and each branch uses `pop af` exactly once before either updating a bound or
returning the result. That balance keeps the stack where it started.

## Instructions in this Lecture

- Z80: [`ld`](https://asm-editor.specy.app/documentation/z80/instruction/ld.md), [`cp`](https://asm-editor.specy.app/documentation/z80/instruction/cp.md), [`jr`](https://asm-editor.specy.app/documentation/z80/instruction/jr.md), [`add`](https://asm-editor.specy.app/documentation/z80/instruction/add.md), [`srl`](https://asm-editor.specy.app/documentation/z80/instruction/srl.md), [`push`](https://asm-editor.specy.app/documentation/z80/instruction/push.md), [`inc`](https://asm-editor.specy.app/documentation/z80/instruction/inc.md), [`pop`](https://asm-editor.specy.app/documentation/z80/instruction/pop.md), [`halt`](https://asm-editor.specy.app/documentation/z80/instruction/halt.md)

Previous: [A jump table](https://asm-editor.specy.app/learn/courses/z80/examples/jump-table.md)

Next: [A 2D array](https://asm-editor.specy.app/learn/courses/z80/examples/two-dimensional-array.md)