Searching an Array – Sequential Search - H-SC

[Pages:29]Searching an Array ? Sequential Search

Lecture 33 Sections 9.1 - 9.2

Robb T. Koether

Hampden-Sydney College

Wed, Nov 28, 2012

Robb T. Koether (Hampden-Sydney College) Searching an Array ? Sequential Search

Wed, Nov 28, 2012 1 / 14

1 Sequential Search 2 The Sequential Search Algorithm 3 Efficiency 4 Assignment

Robb T. Koether (Hampden-Sydney College) Searching an Array ? Sequential Search

Wed, Nov 28, 2012 2 / 14

Outline

1 Sequential Search 2 The Sequential Search Algorithm 3 Efficiency 4 Assignment

Robb T. Koether (Hampden-Sydney College) Searching an Array ? Sequential Search

Wed, Nov 28, 2012 3 / 14

Searching for a Value in an Array

The Problem Locate a value in an array.

Report Whether the value was found, and Where it was found.

Robb T. Koether (Hampden-Sydney College) Searching an Array ? Sequential Search

Wed, Nov 28, 2012 4 / 14

The Sequential Search

If the list is not sorted Use a sequential search. Runs in O(n) time. Relatively inefficient. Suitable for small and medium size lists.

Robb T. Koether (Hampden-Sydney College) Searching an Array ? Sequential Search

Wed, Nov 28, 2012 5 / 14

Outline

1 Sequential Search 2 The Sequential Search Algorithm 3 Efficiency 4 Assignment

Robb T. Koether (Hampden-Sydney College) Searching an Array ? Sequential Search

Wed, Nov 28, 2012 6 / 14

The Sequential Search Algorithm

Make 1 pass. Compare the value to each element. Quit when a match is found or when the end of the list is reached.

Robb T. Koether (Hampden-Sydney College) Searching an Array ? Sequential Search

Wed, Nov 28, 2012 7 / 14

Analysis of the Sequential Search

40 15 63 50 55 90 32 70 36 20 84 64 25 96 48

0

1

2

3

4

5

6

7

8

9 10 11 12 13 14

Robb T. Koether (Hampden-Sydney College) Searching an Array ? Sequential Search

Wed, Nov 28, 2012 8 / 14

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download