Algol 68 searching
last modified November 13, 2026
A search answers where a value is, or that it is not there. The answer is a subscript into a row, and the cost of finding it depends on what the program knows about the row before it starts. A row in no particular order can only be scanned; a sorted row can be halved at every step; a table built for the purpose can jump to the answer almost directly.
This article writes a linear search, an iterative and a recursive binary search, and a small hash table, and it counts the probes that each one needs.
Linear search
The simplest search looks at every element until it finds the value. Algol 68 procedures have no early return, so the position is a variable that the loop fills when it finds a match, and the loop stops as soon as that variable is no longer 0.
PROC find = ([]INT a, INT target) INT:
(
INT pos := 0;
INT i := LWB a;
WHILE pos = 0 AND i <= UPB a DO
IF a[i] = target THEN
pos := i
FI;
i +:= 1
OD;
pos
);
[1:10] INT data := (7, 3, 19, 42, 8, 15, 4, 23, 16, 11);
BEGIN
[1:3] INT targets := (42, 99, 7);
FOR i TO 3 DO
INT target = targets[i];
INT pos = find(data, target);
IF pos = 0 THEN
print((whole(target, 0), " not found", newline))
ELSE
print((whole(target, 0), " found at ", whole(pos, 0), newline))
FI
OD
END
The procedure answers the subscript of the first match, so the caller can use it to read the element or to print it. Because the scan stops at the first match, a row with duplicates yields the leftmost one. A result of 0 means that the value is absent, which is unambiguous for a row whose lower bound is 1.
Both conditions of the loop are comparisons of integers, so the missing
short-circuit evaluation of AND does no harm here: the second test
is safe whatever the first one answers.
$ a68g linear.a68 42 found at 4 99 not found 7 found at 1
Binary search
A binary search needs a sorted row. It compares the target with the middle
element and discards the half that cannot contain it, so every comparison
removes half of what is left. Two variables, lo and hi,
hold the inclusive bounds of the part that is still in play.
PROC binary search = ([]INT a, INT target) INT:
(
INT lo := LWB a;
INT hi := UPB a;
INT pos := 0;
WHILE lo <= hi AND pos = 0 DO
INT mid = (lo + hi) OVER 2;
IF a[mid] = target THEN
pos := mid
ELIF a[mid] < target THEN
lo := mid + 1
ELSE
hi := mid - 1
FI
OD;
pos
);
[1:12] INT data := (2, 5, 8, 12, 16, 23, 38, 56, 72, 91, 104, 120);
BEGIN
[1:4] INT targets := (23, 1, 120, 50);
FOR i TO 4 DO
INT target = targets[i];
INT pos = binary search(data, target);
IF pos = 0 THEN
print((whole(target, 0), " absent", newline))
ELSE
print((whole(target, 0), " at index ", whole(pos, 0), newline))
FI
OD
END
The loop ends when the bounds cross, which means the target is absent, or when
the middle element is the target. The middle is computed with
OVER, which discards the remainder, so an even-length range uses
its left middle. Twelve elements need at most four comparisons.
A result of 0 means absence, as in the linear search, and that convention
assumes a row whose lower bound is 1. A row with lower bound 0 would need a
different signal, such as a separate BOOL, because 0 is then a
valid subscript.
$ a68g binary.a68 23 at index 6 1 absent 120 at index 12 50 absent
A recursive binary search
The same algorithm written as a recursion passes the bounds as parameters. An empty range, where the lower bound has passed the upper one, is the base case and answers 0; every other call compares the middle element and recurses into the half that may still hold the target.
PROC binary search = ([]INT a, INT target, INT lo, hi) INT:
IF lo > hi THEN
0
ELSE
INT mid = (lo + hi) OVER 2;
IF a[mid] = target THEN
mid
ELIF a[mid] < target THEN
binary search(a, target, mid + 1, hi)
ELSE
binary search(a, target, lo, mid - 1)
FI
FI;
[1:9] INT data := (1, 4, 9, 16, 25, 36, 49, 64, 81);
BEGIN
print((whole(binary search(data, 49, 1, 9), 0), newline));
print((whole(binary search(data, 50, 1, 9), 0), newline))
END
The recursion never needs to come back with an answer to combine, because the result of the deeper call is the result of the whole call. A compiler may turn such a tail call into a loop, and the cost in this implementation is one frame per comparison, which stays small because the range halves each time.
The two calls find 49 at subscript 7 and report 0 for 50, which is between 49 and 64. The procedure reads no variables outside its parameters, so several searches can run without interfering with each other.
$ a68g recursive.a68 7 0
Counting probes
The difference between the two searches appears when the row is long. This program builds a row of a thousand even numbers and counts how many elements each search reads before it answers. A probe is one comparison with one element of the row.
INT n = 1000;
INT probes := 0;
PROC linear search = ([]INT a, INT target) INT:
(
INT pos := 0;
INT i := LWB a;
WHILE pos = 0 AND i <= UPB a DO
probes +:= 1;
IF a[i] = target THEN
pos := i
FI;
i +:= 1
OD;
pos
);
PROC binary search = ([]INT a, INT target) INT:
(
INT lo := LWB a;
INT hi := UPB a;
INT pos := 0;
WHILE lo <= hi AND pos = 0 DO
INT mid = (lo + hi) OVER 2;
probes +:= 1;
IF a[mid] = target THEN
pos := mid
ELIF a[mid] < target THEN
lo := mid + 1
ELSE
hi := mid - 1
FI
OD;
pos
);
[1:n] INT data;
BEGIN
FOR i TO n DO
data[i] := i * 2
OD;
probes := 0;
print((whole(linear search(data, 2000), 0), " ",
whole(probes, 0), newline));
probes := 0;
print((whole(binary search(data, 2000), 0), " ",
whole(probes, 0), newline));
probes := 0;
print((whole(binary search(data, 2), 0), " ",
whole(probes, 0), newline))
END
The linear search reads all thousand elements to decide that 2000, the last one, is present, and would read all thousand for a value that is absent as well. The binary search needs ten probes for the same value, because ten halvings take the range from a thousand down to one. Finding the first element costs nine probes, since the search keeps taking the left half.
Ten probes for a thousand elements, and twenty for a million, is the reason a sorted row is worth the effort of sorting. The count grows with the logarithm of the length, while the count of the linear search grows with the length itself.
$ a68g probes.a68 1000 1000 1000 10 1 9
A hash table with rows
A hash table computes the place where a key should be from the key itself, so
a lookup does not depend on the length of the row. The table here is a row of
integers, 0 marks a free slot, and the keys are positive. The procedure
hash reduces a key modulo the size of the table, and a key whose
slot is taken moves to the next slot, wrapping around at the end.
INT size = 13;
PROC hash = (INT key) INT: key MOD size;
PROC insert = (REF []INT t, INT key) VOID:
(
INT i := hash(key);
WHILE t[i] /= 0 DO
i := (i + 1) MOD size
OD;
t[i] := key
);
PROC lookup = ([]INT t, INT key) INT:
(
INT i := hash(key);
INT found := -1;
WHILE found = -1 AND t[i] /= 0 DO
IF t[i] = key THEN
found := i
FI;
i := (i + 1) MOD size
OD;
found
);
[0:size - 1] INT table;
[1:7] INT keys := (13, 26, 39, 7, 20, 33, 100);
BEGIN
FOR i FROM 0 TO size - 1 DO
table[i] := 0
OD;
FOR i TO UPB keys DO
insert(table, keys[i])
OD;
print((whole(hash(13), 0), " ", whole(hash(26), 0), " ",
whole(hash(39), 0), newline));
print((whole(lookup(table, 39), 0), " ", whole(lookup(table, 33), 0),
" ", whole(lookup(table, 5), 0), newline));
FOR i FROM 0 TO size - 1 DO
IF table[i] /= 0 THEN
print((whole(i, -3), ": ", whole(table[i], 0), newline))
FI
OD
END
The keys 13, 26, and 39 all hash to slot 0, so they end up in slots 0, 1, and 2. A lookup follows the same sequence of slots and stops at a free slot, which proves that the key is not in the table. That is why the table must keep at least one slot free: a full table would make both procedures loop forever.
The first line shows the hash values of the three colliding keys, the second shows the slots found for 39 and 33 and the -1 that reports a missing key, and the rest is the table itself. The key 100 hashes to slot 9, finds it free, and stays there. The row is declared without an initialiser, so the program sets every slot to 0 before the first insertion; an element read before it is written holds no useful value.
$ a68g hash.a68 0 0 0 2 9 -1 0: 13 1: 26 2: 39 7: 7 8: 20 9: 33 10: 100
Choosing a search
A linear search is the right choice for a short row or a row that is used once, and it is the only one that works on data in no particular order. A binary search needs sorted data, and sorting costs n log n comparisons, which is worth it when the same row is searched many times. A hash table needs a key that can be reduced to an integer, gives no order, and spends memory on empty slots.
The table of the last example uses open addressing, where every key lives in the row itself. A table with chaining stores a list per slot instead, which the linked lists article makes possible, and the sorting article supplies the sorted row that the binary search expects.
Next steps
The sorting article produces the sorted rows that the binary search needs, and rows explains the bounds and subscripts used throughout this article. Linked lists shows the structure behind a hash table with chaining, and strings covers the text that a search often looks through.
Source
Revised Report on the Algorithmic Language Algol 68
In this article we have searched rows linearly and by halving, written the binary search as a loop and as a recursion, counted the probes that each approach needs, and built a hash table with open addressing in a plain row.
Author
List all Algol 68 tutorials.