# AP® Computer Science A 4.14 Searching Algorithms

Source: https://lockincs.com/ap-csa/unit-4/4-14-searching-algorithms/  
Last reviewed against the College Board Course and Exam Description (CED): 2026-11-12  
CED codes: 4.14.A, 4.14.A.1, 4.14.A.2

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.

## What you will learn

- 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.

## 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.

## Common mix-ups

- Not true: A linear search needs the data to be sorted. 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).
- Not true: You can return -1 inside the loop with an else branch. Returning -1 in an else branch stops the search after the first element. Return -1 only after the loop has checked every element.
- Not true: Searching from the end gives the same answer as searching from the start. 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.

## In 30 seconds

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

## Checkpoint: 4 practice questions

### Question 1

Consider the following method. What value is returned by the call `findLast(new int[] {7, 3, 9, 3, 5}, 3)`?

```java
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;
}
```

- A. 1
- B. 3
- C. -1
- D. 2

**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.

### Question 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?

```java
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;
}
```

- A. `findIndex(nums, 4)`
- B. `findIndex(nums, 10)`
- C. `findIndex(nums, 6)`
- D. `findIndex(nums, 1)`

**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.

### Question 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?

```java
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);
```

- A. 0 1
- B. 1 1
- C. 1 0
- D. -1 -1

**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.

### Question 4

Consider the following code segment. What is printed as a result of executing the code segment?

```java
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);
```

- A. 5
- B. 7
- C. 3
- D. 6

**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.

## 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.

---

© LockInCS, licensed CC BY-NC-ND 4.0. AP® is a trademark registered by the College Board, which is not affiliated with, and does not endorse, this website.