LockInCS

Unit 4 · 15 min

4.14 Searching Algorithms

Linear search is a traversal that stops as soon as it finds what it is looking for.

Summary, objectives and course and exam description (CED) codes

Linear search checks each element in order until it finds the desired value or has checked every element of the array or ArrayList. It can start from either end, and on a two-dimensional (2D) array it searches each row in turn. A linear search method usually returns the index where the value was found, or -1 when it is absent.

By the end of this session you can

  • 4.14.A Develop code used for linear search algorithms to search for specific information in a collection, and determine the results of executing a search.

4.14.A4.14.A.14.14.A.2

Reviewed against the CED on

Know this already? Jump to the checkpoint.

1LearnThe notes, the traps and how to remember them

1. Linear search on an array

A linear search is a standard algorithm that checks each element in order until it finds the desired value or has checked all elements 4.14.A.1. A search method usually returns the index of the target, or -1 when the target is not there. -1 works as a signal because it is never a valid index.

public static int findBib(int[] bibs, int target)
{
    for (int i = 0; i < bibs.length; i++)
    {
        if (bibs[i] == target)
        {
            return i;          // found: stop right away
        }
    }
    return -1;                 // checked every element: not found
}

int[] bibs = {305, 118, 742, 118, 560};
System.out.println(findBib(bibs, 742));
System.out.println(findBib(bibs, 118));
System.out.println(findBib(bibs, 999));

Output:

2
1
-1

Trace of findBib(bibs, 742):

i bibs[i] bibs[i] == 742?
0 305 false
1 118 false
2 742 true: return 2

Watch out: the version below compiles but is wrong. It returns -1 as soon as the first element does not match.

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

int[] bibs = {305, 118, 742, 118, 560};
System.out.println(badFind(bibs, 742));

Output:

-1

2. Linear search on an ArrayList, from either end

The same algorithm works on an ArrayList: use size() and get(i) 4.14.A.1. Use equals to compare objects such as String. A linear search can begin from either end 4.14.A.1: start at the last index and move backward to find the last occurrence.

public static int lastIndexOfTitle(ArrayList<String> titles, String target)
{
    for (int i = titles.size() - 1; i >= 0; i--)
    {
        if (titles.get(i).equals(target))
        {
            return i;
        }
    }
    return -1;
}

ArrayList<String> loans = new ArrayList<String>();
loans.add("Dune");
loans.add("Holes");
loans.add("Dune");
loans.add("Wonder");
System.out.println("last Dune at " + lastIndexOfTitle(loans, "Dune"));
System.out.println("Matilda at " + lastIndexOfTitle(loans, "Matilda"));

Output:

last Dune at 2
Matilda at -1

A forward search for “Dune” would return 0, the first occurrence. Watch out: starting a backward loop at titles.size() throws an IndexOutOfBoundsException on the first get.

3. Linear search on a 2D array

To search a 2D array, access each row, then apply a linear search to that row 4.14.A.2. Return (or store) both the row and the column when you find the target.

public static String findSeat(String[][] seats, String name)
{
    for (int r = 0; r < seats.length; r++)
    {
        String[] row = seats[r];               // access one row
        for (int c = 0; c < row.length; c++)   // linear search on that row
        {
            if (row[c].equals(name))
            {
                return "row " + r + ", seat " + c;
            }
        }
    }
    return "not seated";
}

String[][] seats = { {"Ivy", "Max", "Noor"},
                     {"Leo", "Sam", "Tia"} };
System.out.println(findSeat(seats, "Sam"));
System.out.println(findSeat(seats, "Zed"));

Output:

row 1, seat 1
not seated

4. How many comparisons? (informal run time)

The number of comparisons a linear search makes depends on where the target is 4.14.A.1. Counting them is a useful way to compare algorithms informally, and it prepares you for binary search in topic 4.17.

public static int countChecks(int[] data, int target)
{
    int checks = 0;
    for (int i = 0; i < data.length; i++)
    {
        checks++;
        if (data[i] == target)
        {
            return checks;
        }
    }
    return checks;
}

int[] data = {8, 3, 9, 1, 6, 4, 7, 2};
System.out.println("target 8: " + countChecks(data, 8));
System.out.println("target 6: " + countChecks(data, 6));
System.out.println("target 5: " + countChecks(data, 5));

Output:

target 8: 1
target 6: 5
target 5: 8
Case Where the target is Comparisons for n elements
Best case first element checked 1
Worst case last element checked, or absent n

Double the number of elements and the worst case doubles too.

Lock it in: memory hooks

  • Linear searchLike checking every locker in a hallway, one by one, until you find your name.
  • Where -1 goesGive up only after the last locker: return -1 after the loop, never inside it.
  • 2D searchRow by row: grab a row, linear search it, then grab the next row.

Common misconceptions

  • "A linear search needs the data to be sorted."

    Not quite. Linear search works on any data, sorted or not, because it checks every element in turn. Binary search is the algorithm that needs sorted data (topic 4.17).

  • "You can return -1 inside the loop with an else branch."

    Not quite. Returning -1 in an else branch stops the search after the first element. Return -1 only after the loop has checked every element.

  • "Searching from the end gives the same answer as searching from the start."

    Not quite. When the value appears more than once, a search from the front finds the first occurrence and a search from the back finds the last one.

Exam traps

  • Compare String and other objects with equals, not ==.
  • An else branch that returns -1 inside the loop ends the search after one element.
  • A backward search must start at length - 1 (or size() - 1), not at length.
  • In the worst case (target absent or in the last position checked) linear search makes one comparison per element.

2PracticeRecall it, then check yourself

In 30 seconds

  1. Linear search checks elements one at a time, in order, until it finds the target or runs out of elements.
  2. It works on unsorted data, on arrays and on ArrayLists.
  3. It can start from index 0 (first occurrence) or from the last index (last occurrence).
  4. Return the index as soon as you find the target; return -1 after the loop if it was never found.
  5. On a 2D array, access each row, then run a linear search on that row.

Cover this list, say the points out loud, then take the checkpoint without scrolling back up.

Checkpoint · 4 questions

Checkpoint: Searching Algorithms

Pick an answer to mark it. Every answer is explained, and you can try any question again. Your saved score counts first tries only, and stays in this browser.

  1. 1 Consider the following method. What value is returned by the call findLast(new int[] {7, 3, 9, 3, 5}, 3)? 4.14.A.1 
    public static int findLast(int[] arr, int target)
{
    for (int i = arr.length - 1; i >= 0; i--)
    {
        if (arr[i] == target)
        {
            return i;
        }
    }
    return -1;
}
    Show answer

    Answer: B. The linear search starts at the last index and moves toward index 0, so it stops at the last occurrence of 3, which is at index 3. 1 is the first occurrence, which a forward search would return. -1 would mean 3 is absent, and 2 is the index of 9.

  2. 2 The following method is intended to return the index of target in nums, or -1 if target is not in nums. Assume nums contains the values 4, 6 and 8, in that order. Which of the following calls does NOT return the intended value? 4.14.A.1 
    public static int findIndex(int[] nums, int target)
{
    for (int i = 0; i < nums.length; i++)
    {
        if (nums[i] == target)
        {
            return i;
        }
        else
        {
            return -1;
        }
    }
    return -1;
}
    Show answer

    Answer: C. The else branch returns -1 as soon as the first element does not match, so only index 0 is ever checked. findIndex(nums, 6) returns -1 even though 6 is at index 1. The call with 4 correctly returns 0, and the calls with 10 and 1 correctly return -1 because those values are absent.

  3. 3 Consider the following code segment, which searches a 2D array of animal names. What is printed as a result of executing the code segment? 4.14.A.2 
    String[][] pens = { {"ox", "cat"},
                    {"dog", "cat"} };
int foundRow = -1;
int foundCol = -1;
boolean found = false;
for (int r = 0; r < pens.length && !found; r++)
{
    for (int c = 0; c < pens[r].length && !found; c++)
    {
        if (pens[r][c].equals("cat"))
        {
            foundRow = r;
            foundCol = c;
            found = true;
        }
    }
}
System.out.println(foundRow + " " + foundCol);
    Show answer

    Answer: A. The search accesses each row in turn and runs a linear search across it. In row 0 it reaches "cat" at column 1 and the found flag stops both loops, so it prints 0 1. 1 1 is the second "cat", which the search never reaches. 1 0 swaps the row and column, and -1 -1 would mean "cat" was never found.

  4. 4 Consider the following code segment. What is printed as a result of executing the code segment? 4.14.A.1 
    ArrayList<String> roster = new ArrayList<String>();
roster.add("Ana");
roster.add("Ben");
roster.add("Cleo");
roster.add("Dev");
roster.add("Eli");
roster.add("Fay");
int checks = 0;
int index = -1;
for (int i = 0; i < roster.size() && index == -1; i++)
{
    checks++;
    if (roster.get(i).equals("Omar"))
    {
        index = i;
    }
}
System.out.println(checks);
    Show answer

    Answer: D. "Omar" is not in the list, so the linear search must check every element before it can stop: 6 calls to equals, one per element. 5 would stop one element early, 7 checks an element that does not exist, and 3 is half the list, which is how many checks are needed only when the target is in the middle.

3PrevailLock it in for exam day

By the numbers

Name each list from memory, then reveal it to check. Each list shows how many items to recall.

  • Places a linear search can start two ends CED 4.14.A.1
    1. the first elementindex 0
    2. the last element (index length - 1 or size() - 1)
  • Ways a linear search ends two ways CED 4.14.A.1
    1. the desired value is found
    2. all elements have been checked

Key terms: flip the cards

Read the term, say the definition out loud, then flip to check. Struggling a little to remember is what makes it stick.

  • Linear searchtap to flip

    A search algorithm that checks each element in order until it finds the desired value or has checked every element.

    Example and CED codes
  • Binary searchtap to flip

    A search algorithm for sorted data that checks the middle element and eliminates half of the remaining elements each step.

    Example and CED codes
  • Arraytap to flip

    An object that stores a fixed number of values of the same type, either primitive values or object references, reached by an index.

    Example and CED codes
  • ArrayListtap to flip

    A java.util class for a list of object references that can grow and shrink; ArrayList<E> names the element type E.

    Example and CED codes
  • 2D arraytap to flip

    An array of arrays that stores related data in rows and columns; each element is reached with arr[row][col].

    Example and CED codes
  • Traversaltap to flip

    Using repetition (or recursion) to access all elements of an array or ArrayList, or an ordered sequence of them.

    Example and CED codes

Questions students ask

What is linear search in Java?

Linear search is an algorithm that checks each element of an array or ArrayList in order until it finds the value it is looking for or has checked every element.

Why does linear search return -1?

Valid indexes start at 0, so -1 can never be a real position. Returning -1 tells the caller that the value is not in the collection.

How do you search a 2D array for a value?

Use an outer loop over the rows. For each row, run a linear search across its columns. Return or record the row and column when you find the value.

How many comparisons does a linear search make?

It depends on where the target is: 1 comparison if it is the first element checked, and one comparison per element (n comparisons for n elements) if it is the last element checked or not there at all.

Was this page helpful?

No names are ever shown, and every public comment is checked by us first. Please do not include personal details. To get a reply, email [email protected].

↑ Top

Enlarged view of the selected figure