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