4.14 - Searching Algorithms

Linear search checks each element in order until it finds the value it’s looking for, or it runs out of elements to check. You can start the search from either end.


int[] nums = {4, 8, 15, 16, 23};
int target = 15;
int foundIndex = -1;

for (int i = 0; i < nums.length; i++) {
    if (nums[i] == target) {
        foundIndex = i;
        break;
    }
}

On the exam, linear search is usually written as a method that returns the index where the value was found, or -1 if it isn’t there. Returning from inside the loop stops the search the moment the value is found:


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

Calling linearSearch(nums, 16) on {4, 8, 15, 16, 23} checks 4, 8, 15, then 16, so it makes 4 comparisons and returns 3. Searching for a value that isn’t there, like 5, checks all 5 elements and returns -1. Linear search works on any data, sorted or not.

Starting from the other end just means looping backward. This version finds the last place the value appears:


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

For an ArrayList, use size() and get(i). When the elements are objects like Strings, compare with equals, not ==:


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

For a 2D array, you’d apply linear search row by row, accessing each row and then searching through it.


int[][] grid = { {1, 2, 3}, {4, 5, 6} };
int target = 5;
boolean found = false;

for (int[] row : grid) {
    for (int val : row) {
        if (val == target) {
            found = true;
        }
    }
}

Since each row is a 1D array, you can also access each row and run the 1D linearSearch method on it:


public static boolean contains(int[][] grid, int target) {
    for (int[] row : grid) {
        if (linearSearch(row, target) != -1) {
            return true;
        }
    }
    return false;
}

Back Next