Searching Algorithms

⚠ Optional chapter. This chapter deepens the array/2D-array work from Ch.9/Ch.10 with two classic algorithms — informational, not required for FRC programming itself.

Linear (Sequential) Search

Linear search checks each element in order until it finds the target or runs out of elements — the same "check every element" shape from Ch.9.5, applied specifically to finding a value:

public static int sequentialSearch(int[] canBusIds, int target)
{
    for (int j = 0; j < canBusIds.length; j++)
    {
        if (canBusIds[j] == target)
        {
            return j;
        }
    }
    return -1; // not found
}

Searching for a String (like an autonomous route name) needs .equals() instead of == (Lesson 6.1/13) — comparing object content, not identity.

Linear search's slowest case is a target that isn't present at all — the loop has to check every single element before concluding that. Its fastest case is the target sitting at index 0.

Linear Search Over a 2D Array

Extending linear search to a 2D array (Ch.10) just means looping through every row and searching within it — the same nested-loop shape from Ch.10.3:

public static boolean containsFault(double[][] moduleCurrents, double faultValue)
{
    for (int row = 0; row < moduleCurrents.length; row++)
    {
        for (int col = 0; col < moduleCurrents[0].length; col++)
        {
            if (moduleCurrents[row][col] == faultValue)
            {
                return true;
            }
        }
    }
    return false;
}

Binary Search: Only Works on Sorted Data

Binary search is dramatically faster than linear search, but only works on data that's already sorted — like looking up a name in a phone book by jumping to roughly the right spot, instead of checking every page from the start. It keeps left/right bounds, checks the middle element, and eliminates half the remaining range every time:

public static int binarySearch(int[] sortedTemps, int target)
{
    int left = 0;
    int right = sortedTemps.length - 1;
    while (left <= right)
    {
        int middle = (left + right) / 2;
        if (target < sortedTemps[middle])
        {
            right = middle - 1; // target must be in the left half
        }
        else if (target > sortedTemps[middle])
        {
            left = middle + 1;  // target must be in the right half
        }
        else
        {
            return middle;      // found it
        }
    }
    return -1; // left > right means the range is exhausted — not found
}

For a String[], compareTo replaces </> (which only work on primitives): str.compareTo(other) returns negative, zero, or positive depending on whether str sorts before, equal to, or after other.

Why Binary Search Is So Much Faster

Linear search's worst case takes n comparisons for n elements. Binary search's worst case only takes roughly log₂(n) — each comparison eliminates half the remaining data, not just one element:

Doubling the data size costs linear search twice the work, but only costs binary search one more comparison. This growth-rate distinction — O(n) vs. O(log n) in formal terms — is why sorted, frequently-searched data (a large lookup table, a big sorted config file) is worth keeping sorted specifically so binary search stays available.

Common Pitfalls

• Running binary search on unsorted data. It will return wrong or missing results — binary search's entire correctness depends on the data already being sorted.
• Assuming binary search requires integers. It works on anything with a well-defined ordering — Strings via compareTo, for instance.
• Forgetting the loop-ending condition. Binary search's while (left <= right) stops the moment the range is exhausted (left > right) — a search for something not present must still terminate, not loop forever.

Key Takeaways

• Linear search checks every element in order; its worst case (not found) requires checking all n elements.
• Binary search only works on sorted data, but eliminates half the remaining range with each comparison — roughly log₂(n) comparisons worst case, vastly faster for large data sets.
• Use .equals()/compareTo() for String comparisons in either algorithm, never ==/</>.
• The gap between linear and binary search's growth rates is exactly why sorted data (Lesson 28.2 covers how to get it that way) is worth maintaining when it's searched often.

Derived from csawesome-2026: unit-4-data-collections/4.14-searching-algorithms.md (CSA 4.14)