Array list: find

Algorithmic problem: Ordered sequence: find

Prerequisites: None.

Type of algorithm: loop

Auxiliary data: A pointer $\text{[math]}$ of type "pointer to list item of array lists of component type $\text{[math]}$ ".

Abstract view

Invariant: After $\text{[math]}$ iterations:

The pointer $\text{[math]}$ points to the list item at position $\text{[math]}$ (or is void if no such item exists).
The first $\text{[math]}$ arrays in the list do not contain $\text{[math]}$ .

Variant: The pointer $\text{[math]}$ is moved one step forward to the next array list item.

Break condition: Either $\text{[math]}$ void or, otherwise, $\text{[math]}$ .

Abstract view: Set $\text{[math]}$ first.

Implementation: Obvious.

Proof: Nothing to show.

Abstract view:

Terminate the algorithm if the end of the list is reached or, otherwise, if $\text{[math]}$ is found in the current array.
Otherwise, $\text{[math]}$ is moved one step forward to the next array.

Implementation:

If $\text{[math]}$ void, terminate the algorithm and return false.
Otherwise, if $\text{[math]}$ for some $\text{[math]}$ , terminate the algorithms and return true.
Set $\text{[math]}$ .

Correctness: Obvious.

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

Proff: Obvious.