Lesson 5.9

Search a list; find the largest without built-ins

Part 5: Text, lists, stacks and queuesReading, about 5 min3 exercises in this lesson

Java answers can't run on Spine yet. You can still read Java, trace it, and put an answer's lines in order.

Where is it, and which is largest

By the end of this you will be able to search a list for a value and say where it is, or that it is not there, and find the largest value in a list by writing the loop yourself.

Where is it: a search that gives a position

The last search answered yes or no. Often you need more: the position of the value you found. Say you want the position of the first value above a limit.

Visit the positions in order, from 0. The answer is a position, so loop over the indexes, not just the values.
Test the value at each position.
Return the position as soon as a value passes. A return ends the function at once, even from inside a loop, so nothing after the first match is looked at.
After the loop, return -1. That line is reached only when no value passed. A search that walks forward from position 0 only ever returns 0 or more, so -1 can only mean "not found".

def first_above(values, limit):
    for i in range(len(values)):
        if values[i] > limit:
            return i
    return -1

public static int firstAbove(int[] values,
        int limit) {
    for (int i = 0; i < values.length; i++) {
        if (values[i] > limit) {
            return i;
        }
    }
    return -1;
}

With the values 4, 9, 2, 12 and a limit of 5, it returns 1: 9, at position 1, is the first value above 5, and 12 is never looked at. With the values 4, 2 and the same limit, the loop ends without a match and the function returns -1.

Check the answer for -1 before you use it as a position. In Java, values[-1] stops the program with an error. In Python it quietly gives the last value of the list, so the mistake is easy to miss.

A common mistake: returning -1 in an else inside the loop. Then the function gives its answer after the first value, whatever is further on. As in the last reading, a search can say "found" early, but "not found" only after the last value.

The largest, without the shortcuts

Exam questions sometimes ask you to find the largest value without the language's own shortcuts, such as max() in Python or Math.max and sorting in Java. The idea is a largest-so-far that changes only when something beats it.

Start the largest so far at the first value. Before anything else is looked at, it is the largest one seen.
Compare each value with the largest so far, not with the first value.
When a value is bigger, it becomes the new largest so far.
After the loop, the largest so far is the largest of the whole list.

def largest(values):
    best = values[0]
    for value in values:
        if value > best:
            best = value
    return best

public static int largest(int[] values) {
    int best = values[0];
    for (int value : values) {
        if (value > best) {
            best = value;
        }
    }
    return best;
}

With the values 6, 3, 11, 8, the largest so far is 6, then still 6, then 11, then still 11, and the function returns 11. This needs at least one value, because an empty list has no first value to start from. For the smallest, keep a smallest so far and change the test to <.

A common mistake: starting the largest so far at 0 instead of at the first value. With the values -5, -2, -9 nothing is bigger than 0, so the function returns 0, which is not even in the list. Start from a value that really is in the list.

The pattern to remember

A search for a position returns the moment it finds a match, and returns -1 only after the loop. A largest so far starts at a real value from the list and changes only when a value beats it. Now try it yourself on the questions below.

Exercise 5.9.15.9.1 · Write itFirst repeat in a row

Write a function that searches a list (an array in Java) of whole numbers for the first value that is equal to the value just before it, and returns that value's position (its index). Positions start at 0.

Return the position of the later value of the pair, not the earlier one.
If there is more than one such pair, return the position for the first pair.
If no value is equal to the value just before it, return -1.
The list can be empty, and has at most 20 values. Every value is between -1000 and 1000.

Only the number your function returns is checked.

def first_repeat(values: list[int]) -> int

Examples

Your function is tested on 12 cases: the 4 examples below, and 8 hidden ones that check the rules above.

first_repeat([4, 7, 7, 2]) should return 2: the 7 at position 2 equals the one before it, so 2, the later of the pair (rule 1)
first_repeat([3, 3, 5, 5]) should return 1: two pairs, and the first pair wins (rule 2)
first_repeat([1, 2, 3]) should return -1: no value equals the one before it (rule 3)
first_repeat([]) should return -1: an empty list (rules 3 and 4)

public static int firstRepeat(int[] values)

Running Java here comes later. You can put this answer's lines in order instead. You can still write your Java answer (it stays while this page is open) and compare it with our worked solution. Or try this exercise in Python.Checking whether Java answers can run here.

Examples

Your function is tested on 12 cases: the 4 examples below, and 8 hidden ones that check the rules above.

firstRepeat(new int[]{4, 7, 7, 2}) should return 2: the 7 at position 2 equals the one before it, so 2, the later of the pair (rule 1)
firstRepeat(new int[]{3, 3, 5, 5}) should return 1: two pairs, and the first pair wins (rule 2)
firstRepeat(new int[]{1, 2, 3}) should return -1: no value equals the one before it (rule 3)
firstRepeat(new int[]{}) should return -1: an empty list (rules 3 and 4)

solution.pySolution.java

def first_repeat(values: list[int]) -> int:
    # your code here
    pass

Exercise 5.9.25.9.2 · Write itLargest minus smallest

Write a function that returns the largest value in a list (an array in Java) of whole numbers minus the smallest value in it.

The list always has at least one value, and has at most 20 values.
Every value is between -1000 and 1000, and the values can be negative.
Write the loop yourself. The shortcuts listed with this question are not allowed.

Only the number your function returns is checked.

def spread(values: list[int]) -> int

You cannot use these in this question:

max()
min()
sorted()
.sort()
import heapq
import statistics

Some exam questions ask you to find the largest or smallest yourself, so practise the loop. The shortcuts listed are not allowed.

Examples

Your function is tested on 11 cases: the 4 examples below, and 7 hidden ones that check the rules above.

spread([3, 8, 5]) should return 5: 8 is the largest and 3 the smallest, so 8 - 3
spread([4]) should return 0: one value is both the largest and the smallest (rule 1)
spread([-6, -2, -9]) should return 7: all negative: -2 - (-9) is 7 (rule 2)
spread([10, 1, 7]) should return 9: the largest is first, and a later value is smaller than the first but not the smallest

public static int spread(int[] values)

You cannot use these in this question:

Math.max()
Math.min()
Arrays.sort()
Arrays.parallelSort()
Arrays.stream()
Collections.max()
Collections.min()
IntStream.of()
.sort()
.stream()
.max()
.min()
.summaryStatistics()
import java.util.stream

Some exam questions ask you to find the largest or smallest yourself, so practise the loop. The shortcuts listed are not allowed.

Examples

Your function is tested on 11 cases: the 4 examples below, and 7 hidden ones that check the rules above.

spread(new int[]{3, 8, 5}) should return 5: 8 is the largest and 3 the smallest, so 8 - 3
spread(new int[]{4}) should return 0: one value is both the largest and the smallest (rule 1)
spread(new int[]{-6, -2, -9}) should return 7: all negative: -2 - (-9) is 7 (rule 2)
spread(new int[]{10, 1, 7}) should return 9: the largest is first, and a later value is smaller than the first but not the smallest

solution.pySolution.java

def spread(values: list[int]) -> int:
    # your code here
    pass

Exercise 5.9.35.9.3 · Write itPosition of the largest

Write a function that returns the position (the index) of the largest value in a list (an array in Java) of whole numbers. Positions start at 0.

If the largest value appears more than once, return the position of the first one.
The list always has at least one value.
The values can be negative.
Write the search yourself. The shortcuts listed with this question are not allowed.

Only the number your function returns is checked.

def index_of_largest(values: list[int]) -> int

You cannot use these in this question:

max()
min()
sorted()
.index()
.sort()
import heapq

Some exam questions ask you to write the search yourself, so practise the loop. The shortcuts listed are not allowed.

Examples

Your function is tested on 10 cases: the 5 examples below, and 5 hidden ones that check the rules above.

index_of_largest([4, 9, 2]) should return 1: 9 is the largest, at position 1
index_of_largest([7]) should return 0: one value, so position 0
index_of_largest([9, 1, 9]) should return 0: the first 9 wins (rule 1)
index_of_largest([-5, -2, -9]) should return 1: all negative values (rule 3)
index_of_largest([1, 5, 3]) should return 1: a later value smaller than the best so far

public static int indexOfLargest(int[] values)

You cannot use these in this question:

Math.max()
Math.min()
Arrays.sort()
Arrays.parallelSort()
Collections.max()
Collections.min()
.indexOf()
.sort()
.stream()
.max()
.min()
import java.util.stream

Some exam questions ask you to write the search yourself, so practise the loop. The shortcuts listed are not allowed.

Examples

Your function is tested on 10 cases: the 5 examples below, and 5 hidden ones that check the rules above.

indexOfLargest(new int[]{4, 9, 2}) should return 1: 9 is the largest, at position 1
indexOfLargest(new int[]{7}) should return 0: one value, so position 0
indexOfLargest(new int[]{9, 1, 9}) should return 0: the first 9 wins (rule 1)
indexOfLargest(new int[]{-5, -2, -9}) should return 1: all negative values (rule 3)
indexOfLargest(new int[]{1, 5, 3}) should return 1: a later value smaller than the best so far

solution.pySolution.java

def index_of_largest(values: list[int]) -> int:
    # your code here
    pass