Array list: find

From Algowiki
Jump to navigation Jump to search

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 K".

Abstract view

Invariant: After i0 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 K.

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

Break condition: Either p=void or, otherwise, K{p.A[1],,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 K 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]=K for some j{1,,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.