# Array list: find

Algorithmic problem: Ordered sequence: find

Prerequisites: None.

Type of algorithm: loop

Auxiliary data: A pointer $p$ of type "pointer to list item of array lists of component type $\Kappa$".

## Abstract view

Invariant: After $i \ge 0$ iterations:

1. The pointer $p$ points to the list item at position $i + 1$ (or is void if no such item exists).
2. The first $i$ arrays in the list do not contain $\Kappa$.

Variant: The pointer $p$ is moved one step forward to the next array list item.

Break condition: Either $p=$void or, otherwise, $\Kappa \in \{p.A[1], \ldots, p.A[p.n]\}$.

## Induction basis

Abstract view: Set $p:=$ first.

Implementation: Obvious.

Proof: Nothing to show.

## Induction step

Abstract view:

1. Terminate the algorithm if the end of the list is reached or, otherwise, if $\Kappa$ is found in the current array.
2. Otherwise, $p$ is moved one step forward to the next array.

Implementation:

1. If $p=$void, terminate the algorithm and return false.
2. Otherwise, if $p.A[j] = \Kappa$ for some $j \in \{1, \ldots, p.n\}$, terminate the algorithms and return true.
3. Set $p:=p.next$.

Correctness: Obvious.

## Complexity

Statement: Linear in the length of the sequence in the worst case.

Proff: Obvious.