Array list: find

From Algowiki
Jump to: navigation, search

Algorithmic problem: Ordered sequence: find

Prerequisites: None.

Type of algorithm: loop

Auxiliary data: A pointer of type "pointer to list item of array lists of component type ".

Abstract view

Invariant: After iterations:

  1. The pointer points to the list item at position (or is void if no such item exists).
  2. 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, .

Induction basis

Abstract view: Set 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 is found in the current array.
  2. Otherwise, is moved one step forward to the next array.

Implementation:

  1. If void, terminate the algorithm and return false.
  2. Otherwise, if for some , terminate the algorithms and return true.
  3. Set .

Correctness: Obvious.

Complexity

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

Proff: Obvious.