# Binary search

[Courses](https://asm-editor.specy.app/learn/courses.md) › [RISC-V assembly](https://asm-editor.specy.app/learn/courses/risc-v.md) › Examples

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

> Find a value in a sorted array by maintaining an inclusive range and discarding half after each midpoint probe.

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), [Z80](https://asm-editor.specy.app/learn/courses/z80/examples/binary-search.md), [x86-64](https://asm-editor.specy.app/learn/courses/x86/examples/binary-search.md)

The array contains twelve numbers in ascending order. This program finds the index of 91 by
repeatedly cutting the possible range in half. It leaves the index in `t4`, or -1 if the target is
absent.

The range includes both ends: `low` and `high` are possible indices. The idea that keeps the search
correct is:

> Each time execution reaches `search`, if the target is in the array, it is somewhere from
> `numbers[low]` through `numbers[high]`.

Ascending order justifies both ways of shrinking that range:

| comparison at `mid`     | what ascending order tells us                     | new possible range |
| ----------------------- | ------------------------------------------------- | ------------------ |
| `numbers[mid] < target` | every element through `mid` is also too small     | `low = mid + 1`    |
| `numbers[mid] > target` | every element from `mid` onward is also too large | `high = mid - 1`   |

Here are the register roles. `t6` is scratch space: it holds the byte offset, then the address, and
finally the value loaded from that address.

| register | role                                       |
| -------- | ------------------------------------------ |
| `t0`     | base address of `numbers`                  |
| `t1`     | target value                               |
| `t2`     | `low`, the first possible index            |
| `t3`     | `high`, the last possible index            |
| `t4`     | answer, initially -1                       |
| `t5`     | `mid`, the index being inspected           |
| `t6`     | scratch space for accessing `numbers[mid]` |

```riscv
.eqv COUNT, 12

.data
numbers: .word 2, 5, 8, 12, 16, 23, 38, 56, 72, 91, 100, 127

.text
main:
    la t0, numbers          # base address of the array
    li t1, 91               # target
    li t2, 0                # low = 0
    li t3, COUNT
    addi t3, t3, -1         # high = COUNT - 1
    li t4, -1               # answer = -1, meaning absent
search:
    bgt t2, t3, search_done # while (low <= high)
    add t5, t2, t3
    srli t5, t5, 1          # mid = (low + high) / 2
    slli t6, t5, 2          # byte offset = mid * 4
    add t6, t0, t6          # address of numbers[mid]
    lw t6, 0(t6)            # value = numbers[mid]
    beq t6, t1, found
    bgt t6, t1, too_big
    addi t2, t5, 1          # value < target: low = mid + 1
    j search
too_big:
    addi t3, t5, -1         # value > target: high = mid - 1
    j search
found:
    mv t4, t5               # answer = mid
search_done:
```

At the start, `low` is 0 and `high` is `COUNT - 1`, so both name valid array indices. The loop body
runs only while `low <= high`. In this twelve-element program, their sum is nonnegative and small,
so shifting it right by one computes `(low + high) / 2`, rounded down. That result is a valid index
inside the current range.

Every element access uses `slli` to multiply `mid` by the four-byte size of each `.word` element,
adds the array's base address, and then uses `lw` to read the element. The `lw` writes over the
address in `t6` because the program no longer needs that address.

Here is the range closing on the answer. Each row corresponds to one trip through the loop body:

| probe | `low` | `high` | `mid` | `numbers[mid]` | branch result             |
| ----- | ----- | ------ | ----- | -------------- | ------------------------- |
| 1     | 0     | 11     | 5     | 23             | `23 < 91`, so `low = 6`   |
| 2     | 6     | 11     | 8     | 72             | `72 < 91`, so `low = 9`   |
| 3     | 9     | 11     | 10    | 100            | `100 > 91`, so `high = 9` |
| 4     | 9     | 9      | 9     | 91             | equal, so `t4 = 9`        |

This search reads four elements. A left-to-right search for this particular target would read ten,
because 91 is at index 9. More generally, binary search needs at most 10 midpoint probes for 1,000
sorted elements and at most 20 for 1,000,000.

To see the failure result, change `li t1, 91` to `li t1, 90` and run the program again. The possible
range eventually becomes empty: `low` is greater than `high`, so execution reaches `search_done`.
No instruction has replaced the initial -1 in `t4`. In a 32-bit register, the simulator displays
that value as `0xFFFFFFFF`, the all-one bit pattern for -1. Zero cannot serve as the failure marker
because index 0 belongs to the first array element.

## Exercise

Start from the working program and make these small tests:

1. Change the target to 2 and predict the final value of `t4`. Run it and check your prediction.
2. Repeat with 127, the last element, and then with 90, which is absent.
3. Add `.word 90` immediately after the twelve array values, but leave `COUNT` as 12. Search for 90
   again. It is a sentinel just beyond the array, so a correct search must still leave -1 in `t4`.
4. Before running the 90 search, make a table with columns for `low`, `high`, `mid`, and
   `numbers[mid]`. Fill one row for every probe, then compare it with a step-by-step run.
5. Finally, hide the two bound-update lines, `addi t2, t5, 1` and `addi t3, t5, -1`, with comments.
   Restore them from the rule: a middle value that is too small moves `low`; one that is too large
   moves `high`.

## Instructions in this Lecture

- RISC-V: [`la`](https://asm-editor.specy.app/documentation/risc-v/instruction/la.md), [`li`](https://asm-editor.specy.app/documentation/risc-v/instruction/li.md), [`addi`](https://asm-editor.specy.app/documentation/risc-v/instruction/addi.md), [`bgt`](https://asm-editor.specy.app/documentation/risc-v/instruction/bgt.md), [`add`](https://asm-editor.specy.app/documentation/risc-v/instruction/add.md), [`srli`](https://asm-editor.specy.app/documentation/risc-v/instruction/srli.md), [`slli`](https://asm-editor.specy.app/documentation/risc-v/instruction/slli.md), [`lw`](https://asm-editor.specy.app/documentation/risc-v/instruction/lw.md), [`beq`](https://asm-editor.specy.app/documentation/risc-v/instruction/beq.md), [`j`](https://asm-editor.specy.app/documentation/risc-v/instruction/j.md), [`mv`](https://asm-editor.specy.app/documentation/risc-v/instruction/mv.md)

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

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