Java Reference

In-Depth Information

8.5

Basic array algorithms

There are a few fundamental array algorithms that programmers should know:

Lessons

8-5..6

• linear search, for finding the first occurrence of a value in an array.

• finding the minimum value in an array.

• inserting a value into a sorted (in non-descending order) segment.

• partitioning an array.

• merging two sorted array segments.

• binary search for a value in an ordered array.

• insertion sort.

• selection sort.

See lesson

pages 8-5..6 to

get these algo-

rithms.

We show some of the algorithms here; the rest can be found in
ProgramLive
.

It is difficult to memorize the code for these algorithms. Instead,
memorize

the loop invariant and develop the algorithm from the invariant whenever nec-

essary
. Here is a less threatening way to say that: remember the pictures and

develop code based on them.

8.5.1

Linear search

We develop an algorithm to satisfy this specification:

Activities

8-5.1..2

/** =
the index of the first occurrence of
v
in
b[h..k-1]

—or
k
if
v
is not in
b[h..k-1] */

public static int
linearSearch(
int
[] b,
int
h,
int
k,
int
v)

How will this function be used?
Examples when
d={3
,
5
,
1
,
7
,
3
,
8}
:

call

result

linearSearch(d
,
0
,
2
,
3)

0

linearSearch(d
,
0
,
2
,
4)

2

linearSearch(d
,
4
,
6
,
8)

5

linearSearch(d
,
4
,
6
,
2)

6

linearSearch(d
,
4
,
4
,
2)

4

Activity 8-5.1 of
ProgramLive
explains linear search by giving the invariant

in terms of math formulas. Here, we draw diagrams. There are two possible post-

conditions of the method (we show only the part
b[h..k-1]
of the array):

h

i

k

Post
1
:

v
not in here

v

b

h

k,i

Post
2
:

v
not in here

b

Search WWH ::

Custom Search