Aim for FiveComputer Science A

Unit 4 · Topic 4.14

4.14 Searching Algorithms

Linear search is the simplest way to find something in a collection: check each element in turn until you find it or run out. This topic covers writing linear search for arrays, ArrayLists and 2D arrays, searching from either end, and what to return when the target isn't there.

Key terms

  • linear (sequential) search
  • target
  • return -1 when not found

How linear search works

Linear search, also called sequential search, checks the elements one at a time, in order, until it finds the target or has checked every element. It works on any data, sorted or not, and on arrays and ArrayLists alike.

The usual version returns the index of the first match, or -1 if there's no match. -1 works as a "not found" signal because it can never be a real index.

public static int linearSearch(int[] arr, int target) { for (int i = 0; i < arr.length; i++) { if (arr[i] == target) { return i; } } return -1; }

With {14, 3, 27, 3, 9}, searching for 3 returns 1 (the first 3), searching for 9 returns 4, and searching for 8 returns -1.

Searching from the other end

Linear search can start at either end. Starting from the last index and moving backward finds the last match instead of the first. For the same array, the backward search for 3 returns 3. Pick the direction that matches what the question asks for.

Variations

The basic loop adapts to many questions:

  • Return a boolean (is it there at all?) instead of an index.
  • Search an ArrayList of objects by one attribute, like list.get(i).getName().equals(name), and return the object or its index.
  • Stop at the first element that meets a condition, like the first score below 60, instead of matching an exact value.
  • For strings and other objects, compare with equals, not ==.

Searching a 2D array

To search a 2D array, take each row in turn and run linear search on it. With nested loops, that's a row-major traversal that returns as soon as it finds a match. Only after both loops finish do you know the target isn't there.

Placement of the final return matters. A "not found" return inside the loops, in an else, would give up after checking a single element.

How much work it does

If the target is near the front, linear search finishes quickly. In the worst case, when the target is last or missing, it checks every element, so a list twice as long can take twice as many checks. Binary search (4.17) is usually much faster, but it needs sorted data.

Worked examples

Try each one yourself first, then open the solution.

  1. Example 1

    Counting checks

    This version of linear search returns how many elements it checked. With data = {14, 3, 27, 3, 9}, what do countChecks(data, 3), countChecks(data, 9) and countChecks(data, 8) return?public static int countChecks(int[] arr, int target) { int checks = 0; for (int i = 0; i < arr.length; i++) { checks++; if (arr[i] == target) { return checks; } } return checks; }

    Show the solution
    1. Step 1: Searching for 3: checks 14 (no), then 3 (yes). It stops at the first match: 2 checks.
    2. Step 2: Searching for 9: it has to check all five elements, and the match is the last one: 5 checks.
    3. Step 3: Searching for 8: no element matches, so it checks all five and then returns: 5 checks.

    Answer: They return 2, 5 and 5.

  2. Example 2

    Write a method: searching a seating chart

    A seating chart is a 2D array of names. Write findSeat to return the position of name as text like row 1, seat 1, or not found. One solution:public static String findSeat(String[][] chart, String name) { for (int r = 0; r < chart.length; r++) { for (int c = 0; c < chart[r].length; c++) { if (chart[r][c].equals(name)) { return "row " + r + ", seat " + c; } } } return "not found"; }

    Show the solution
    1. Step 1: Run linear search on each row in turn: the outer loop picks a row, and the inner loop checks each seat in it.
    2. Step 2: Compare names with equals.
    3. Step 3: Return the position as soon as you find a match. That ends both loops at once.
    4. Step 4: Return "not found" only after both loops finish.
    5. Step 5: With rows {Ava, Ben, Cal} and {Dee, Eli, Fay}, Eli is in row 1, seat 1. Gus isn't anywhere.

    Answer: The method above. It returns row 1, seat 1 for Eli and not found for Gus.

Common mistakes

  • Returning -1 (or false) in an else inside the loop, which quits after the first element.
  • Comparing strings or objects with == instead of equals.
  • Expecting linear search to need sorted data. It doesn't; binary search does.

On the exam

  • Expect questions asking how many elements a search checks, or what it returns when the target appears twice or not at all.

Connected topics

Videos

Check yourself

3 questions on 4.14 Searching Algorithms. Pick an answer to see if you got it, and why.

Question 1 of 3

Consider the following method.public static int lastIndexOf(int[] arr, int target) { for (int i = arr.length - 1; i >= 0; i--) { if (arr[i] == target) { return i; } } return -1; }Assume nums is the array {4, 7, 2, 7, 9}. What is printed by System.out.println(lastIndexOf(nums, 7) + " " + lastIndexOf(nums, 5));?

Question 2 of 3

The following method is intended to return the index of target in arr, or -1 if it isn't there.public static int find(int[] arr, int target) { for (int i = 0; i < arr.length; i++) { if (arr[i] == target) { return i; } else { return -1; } } return -1; }For which of the following calls does the method NOT return the correct result?

Question 3 of 3

Consider the following method.public static String locate(String[][] board, String target) { for (int r = 0; r < board.length; r++) { for (int c = 0; c < board[r].length; c++) { if (board[r][c].equals(target)) { return r + "," + c; } } } return "none"; }Assume board is {{"X", "O", "O"}, {"O", "X", "X"}}. What is returned by locate(board, "X") + " " + locate(board, "Z")?

0 of 3 answered