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