Searching Algorithms FRQ Practice

Responses receive AI feedback against a rubric after submission. Scores are practice estimates.

Question 1 of 5

A ferry office stores passenger counts in a 1D array. Write a linear search from index 0 that also counts comparisons.

public static int[] searchFromStart(int[] seats, int target)
{
    /* return {index, checks} with index -1 if missing */
}

(a) Write the loop, the increment of checks, and the equality test. (b) State both returned values for {4, 0, 9} and target 9. (c) State both returned values for the same array and target 5.

Question 2 of 5

A pantry ArrayList stores 11, 4, 11. A linear search looks for 11 from the last index using get.

(a) List the indexes visited in order and the value at each. (b) State the returned index and the comparison count if the search stops at the first match. (c) Explain what last index and size() have to do with the loop start.

Question 3 of 5

A bulletin board is a rectangular 2D array of integer codes. Implement a row-wise linear search.

Board:

row col 0 col 1 col 2
row 0 12 7 5
row 1 3 7 9

(a) Describe the visit order for target 7 when both loops stop at the first match. (b) State the (row, col) found and the comparison count. (c) Repeat (b) for target 9.

Question 4 of 5

Explain found versus not-found behavior for linear search on this ArrayList of Integer values: 6, 2, 8.

(a) Write a loop from index 0 that sets boolean found and int checks. (b) Give found and checks for target 2. (c) Give found and checks for target 1, and explain why checks equals size().

Question 5 of 5

A rectangular seating chart is searched row by row. Write findFromEndRow that still walks rows from top to bottom, but linear-searches each row from the right end of that row.

public static int[] findFromEndRow(int[][] seats, int target)
{
    /* return {row, col} or {-1, -1} */
}

Use {{1, 8, 4}, {8, 2, 3}} and target 8.

(a) Write the outer row loop and the inner loop that starts at seats[r].length - 1. (b) State the returned location and the comparison count. (c) Contrast that location with a left-to-right search of each row for the same target.