Introduction

Searching—finding a specific value or object in a collection—is one of the most fundamental operations in computer science. Topic 4.14 introduces linear search, the simplest and most intuitive searching algorithm.

Linear search examines elements one by one until finding the target value or reaching the end of the collection. While not the fastest search method, linear search works on any collection (sorted or unsorted) and is straightforward to implement. Understanding linear search prepares you for more sophisticated algorithms like binary search in Topic 4.17.

What is Linear Search?

Linear search algorithms are standard algorithms that check each element in order until the desired value is found or all elements in the array or ArrayList have been checked.

Think of it like looking for a book on a shelf by checking each book from left to right until you find the one you want.

Key characteristics:

Linear Search for Arrays

The basic pattern: traverse the array, compare each element to the target value, return when found.

Returning Index of Found Element

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

Convention: Return -1 when element is not found (since -1 is never a valid index).

Example:

int[] numbers = {23, 45, 12, 67, 34};
int index = linearSearch(numbers, 67);  // Returns 3
int missing = linearSearch(numbers, 99);  // Returns -1

Returning Boolean (Found or Not)

public static boolean contains(int[] arr, int target) 
{
    for (int val : arr) 
    {
        if (val == target) 
        {
            return true;
        }
    }
    return false;
}

Searching for Objects

When searching arrays of objects, compare using .equals():

public static int findStudent(Student[] students, String name) 
{
    for (int i = 0; i < students.length; i++) 
    {
        if (students[i].getName().equals(name)) 
        {
            return i;
        }
    }
    return -1;
}

Important: Use .equals() for object comparison, not ==.

Linear Search for ArrayLists

The pattern is identical, but use ArrayList methods:

public static int search(ArrayList<Integer> list, int target) 
{
    for (int i = 0; i < list.size(); i++) 
    {
        if (list.get(i) == target) 
        {
            return i;
        }
    }
    return -1;
}

Using Enhanced For Loop

When you only need to know if the element exists (not its position):

public static boolean contains(ArrayList<String> list, String target) 
{
    for (String str : list) 
    {
        if (str.equals(target)) 
        {
            return true;
        }
    }
    return false;
}

Searching by Object Property

public static Student findByID(ArrayList<Student> students, int id) 
{
    for (Student s : students) 
    {
        if (s.getID() == id) 
        {
            return s;  // Return the actual object
        }
    }
    return null;  // Not found
}

Searching from Either End

Linear search algorithms can begin the search process from either end of the array or ArrayList.

Sometimes starting from the end is useful:

Searching Backwards

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

When to search backwards:

Finding Last Occurrence

public static int lastIndexOf(ArrayList<Integer> list, int target) 
{
    for (int i = list.size() - 1; i >= 0; i--) 
    {
        if (list.get(i) == target) 
        {
            return i;  // Returns last occurrence
        }
    }
    return -1;
}

Example:

ArrayList<Integer> nums = new ArrayList<Integer>();
nums.add(5); nums.add(10); nums.add(5); nums.add(15);
// [5, 10, 5, 15]

int first = search(nums, 5);        // Returns 0
int last = lastIndexOf(nums, 5);     // Returns 2

Linear Search in 2D Arrays

When applying linear search algorithms to 2D arrays, each row must be accessed then linear search applied to each row of the 2D array.

The pattern: use nested loops—outer loop selects row, inner loop searches within that row.

Searching 2D Array (Return Position)

public static int[] search2D(int[][] arr, int target) 
{
    for (int r = 0; r < arr.length; r++) 
    {
        for (int c = 0; c < arr[0].length; c++) 
        {
            if (arr[r][c] == target) 
            {
                return new int[] {r, c};  // Return row and column
            }
        }
    }
    return new int[] {-1, -1};  // Not found
}

Usage:

int[][] grid = {
    {10, 20, 30},
    {40, 50, 60},
    {70, 80, 90}
};

int[] pos = search2D(grid, 50);  // Returns [1, 1]
int[] missing = search2D(grid, 99);  // Returns [-1, -1]

Searching 2D Array (Return Boolean)

public static boolean contains2D(int[][] arr, int target) 
{
    for (int r = 0; r < arr.length; r++) 
    {
        for (int c = 0; c < arr[0].length; c++) 
        {
            if (arr[r][c] == target) 
            {
                return true;
            }
        }
    }
    return false;
}

Searching Specific Row

public static int searchInRow(int[][] arr, int row, int target) 
{
    for (int c = 0; c < arr[0].length; c++) 
    {
        if (arr[row][c] == target) 
        {
            return c;  // Return column index
        }
    }
    return -1;
}

Searching Specific Column

public static int searchInColumn(int[][] arr, int col, int target) 
{
    for (int r = 0; r < arr.length; r++) 
    {
        if (arr[r][col] == target) 
        {
            return r;  // Return row index
        }
    }
    return -1;
}

Complete Examples

Example 1: Find Student with Highest Score

public static Student findTopStudent(ArrayList<Student> students) 
{
    if (students.size() == 0)
    {
        return null;
    }
    
    Student top = students.get(0);
    for (int i = 1; i < students.size(); i++) 
    {
        if (students.get(i).getScore() > top.getScore()) 
        {
            top = students.get(i);
        }
    }
    return top;
}

Example 2: Count Occurrences

public static int countOccurrences(int[] arr, int target) 
{
    int count = 0;
    for (int val : arr) 
    {
        if (val == target) 
        {
            count++;
        }
    }
    return count;
}

Example 3: Find All Positions in 2D Array

public static ArrayList<int[]> findAll2D(int[][] arr, int target) 
{
    ArrayList<int[]> positions = new ArrayList<int[]>();
    
    for (int r = 0; r < arr.length; r++) 
    {
        for (int c = 0; c < arr[0].length; c++) 
        {
            if (arr[r][c] == target) 
            {
                positions.add(new int[] {r, c});
            }
        }
    }
    return positions;
}

Linear Search Efficiency

Linear search examines up to $n$ elements where $n$ is the collection size.

Best case: Target is the first element—1 comparison

Worst case: Target is the last element or not present—$n$ comparisons

Average case: Target is somewhere in the middle—$\frac{n}{2}$ comparisons

Linear search is inefficient for large collections, but it's the only option when:

Common Mistakes

Mistake 1: Using == instead of .equals() for objects

// WRONG for String comparison
if (arr[i] == target) 
{ }

// CORRECT
if (arr[i].equals(target)) 
{ }

Mistake 2: Forgetting to return after finding element

// WRONG - continues searching unnecessarily
for (int i = 0; i < arr.length; i++) 
{
    if (arr[i] == target) 
    {
        System.out.println("Found at " + i);
        // Missing return!
    }
}

Mistake 3: Wrong return type for 2D search

// WRONG - can't return single int for 2D position
public static int search2D(int[][] arr, int target) 
{ }

// CORRECT - return array with row and column
public static int[] search2D(int[][] arr, int target) 
{ }

Practice Problems