Arrays - Finding Max/Min

COMP108 Lectures 2021-02-24

If the dataset is sorted in descending order then the first number is the maximum number.

This is excessive if set is unsorted.

Pseudo-code Examples

Maximum

i = 1
m = 0	# only works for +ve numbers; see next example
while i <= n do
begin
	if A[i] > m then
		m = A[i]
	i++
end
output m

Minimum

i = 1
m = A[1]	# initialise to the first number in the array
while i <= n do
begin
	if A[i] < m then	# this comparison is changed
		m = A[i]
	i++
end
output m

Time Complexity

The time complexity of this algorithm is:

\[O(n)\]

This is as it iterates through every item in the list once.

Finding Location

i = 2	# location of second
loc = 1	# location of first
while i <= n do
begin
	if A[i] > A[loc] then
		loc = i
	i++
end
output loc and A[loc]

This will find the location of the first instance of the largest number.

To find the location of the last location you would use the following:

i = 2	# location of second
loc = 1	# location of first
while i <= n do
begin
	if A[i] >= A[loc] then
		loc = i
	i++
end
output loc and A[loc]

This will update if we come to a new instance of the maximum value.

Finding All Locations of Maximum

Find the first maximum:

m = A[1]
i = 2	# compare A[1] with A[2] in first iteration
while i <= n do
begin
	if A[i] > m then
		m = A[i]
	i = i + 1
end

Then print other locations of m:

i = 1
while i <= n do
begin
	if A[i] == m then
		output i
	i = i + 1
end
output M

Finding First and Second Maximums

m1 = max(A[1],A[2])	# ensure correct order
m2 = min(A[1],A[2])
i = 3	# skip comparing already compared
while i <= n do
begin
	if A[i] > m1 then
	begin
		m2 = m1
		m1 = A[i]
	end
	else if A[i] > m2 then
		m2 = A[i]
	i = i + 1
end 
output m1 and m2

Time Complexity

There is one loop with a constant number of comparisons. This gives a big-$O$ notation of:

\[O(n)\]