Searching Algorithms FRQ Practice

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

Question 1 of 5

A dock catalog stores crate IDs in a 1D array. Write a linear search that starts at index 0 and stops when the target is found.

public static int indexOf(int[] ids, int target)
{
    /* complete the method */
}

(a) Write the loop and the equality test. (b) State what the method should return if the target is missing. (c) For {6, 1, 8, 1} and target 1, state the returned index and the number of comparisons.

Question 2 of 5

A booth ledger stores ticket numbers in an ArrayList<Integer> named tickets. A linear search looks for target 15 from index 0.

tickets contents in order: 4, 15, 9, 15

Complete the trace table, then answer the questions.

i tickets.get(i) Equal to 15? Action
0
1

(a) Fill both rows for a search that breaks on the first match. (b) State the index returned and the comparison count. (c) Explain how the result would change if the search started at the last index instead.

Question 3 of 5

A greenhouse tray is a rectangular 2D array. Write a row-wise linear search: visit row 0 from left to right, then row 1, and so on, stopping at the first match.

public static int[] findCell(int[][] tray, int target)
{
    /* return {row, col} or {-1, -1} if missing */
}

Use tray {{2, 9, 4}, {8, 0, 6}} and target 0.

(a) Write the nested loops and both breaks (or equivalent flags). (b) Explain why breaking only the inner loop is not enough. (c) State the returned indexes and the comparison count.

Question 4 of 5

A linear search may report a found index or report that the value is missing.

(a) Using int[] codes = {11, 3, 8} and target 3, state the found index and the comparison count for a left-to-right search that stops on a match. (b) Repeat for target 5. (c) Write one sentence that describes when a linear search stops.

Question 5 of 5

Write a linear search on an ArrayList that starts at the last index and moves toward index 0.

public static int lastIndexOf(ArrayList<Integer> nums, int target)
{
    /* complete the method */
}

nums contains 2, 9, 4, 9 in that order. Target is 9.

(a) Write the loop from size() - 1 down to 0 using get. (b) State the returned index and the comparison count. (c) Explain why this is still linear search, not a different algorithm.