# Array list: find

From Algowiki

**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:

- 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, .

## Induction basis

**Abstract view:** Set first.

**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.