Array list: find
Algorithmic problem: Ordered sequence: find
Type of algorithm: loop
Auxiliary data: A pointer of type "pointer to list item of array lists of component type ".
Invariant: After iterations:
- The pointer points to the list item at position (or is void if no such item exists).
- The first arrays in the list do not contain .
Variant: The pointer is moved one step forward to the next array list item.
Break condition: Either void or, otherwise, .
Abstract view: Set first.
Proof: Nothing to show.
- Terminate the algorithm if the end of the list is reached or, otherwise, if is found in the current array.
- Otherwise, is moved one step forward to the next array.
- If void, terminate the algorithm and return false.
- Otherwise, if for some , terminate the algorithms and return true.
- Set .
Statement: Linear in the length of the sequence in the worst case.