Array list: find
Jump to navigation
Jump to search
Algorithmic problem: Ordered sequence: find
Prerequisites: None.
Type of algorithm: loop
Auxiliary data: A pointer
Abstract view
Invariant: After
- 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
Break condition: Either
Induction basis
Abstract view: Set
Implementation: Obvious.
Proof: Nothing to show.
Induction step
Abstract view:
- 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.
Implementation:
- If
void, terminate the algorithm and return false. - Otherwise, if
for some , terminate the algorithms and return true. - Set
.
Correctness: Obvious.
Complexity
Statement: Linear in the length of the sequence in the worst case.
Proff: Obvious.