Unit 4.14: Searching

A linear search (or sequential search) checks each element in a collection one by one until a target value is found or all elements have been checked.

Sequential Examination
  • Linear search starts at one end of the array or ArrayList and moves through it systematically. It does not require the data to be sorted.

Task: Performing a linear search to find the index of a target value.

// In the main method ...
int[] nums = {10, 23, 5, 8, 14};
int target = 5;
int foundIndex = -1;

for (int i = 0; i < nums.length; i++) {
    if (nums[i] == target) {
        foundIndex = i;
        break; // Stop once the target is found
    }
}

Diagram: Linear Search in a 1D Array

Linear Search on a 2D Array

When applying linear search to 2D arrays, each row must be accessed and then a linear search is applied to that row.

Nested Search
  • Searching a 2D array typically requires nested loops: the outer loop visits each row, and the inner loop checks every element within that row.

Task: Searching for a target value in a 2D array using nested loops.

// In the main method ...
int[][] grid = {
    {1, 2, 3},
    {4, 5, 6}
};
int goal = 5;
boolean found = false;

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

Diagram: Linear Search in a 2D Array

Exclusion Statement: Search algorithms other than linear search and binary search are outside the scope of the AP Computer Science A course and exam.