Searching Algorithms

Hello everyone, I'm Saavi, and I'm glad you're here. Let's talk about one of the most fundamental ideas in programming: finding things.

At its heart, a linear search is exactly what it sounds like: you search for something by moving in a straight line from start to finish. It’s the "brute force" way of searching, but don't let that fool you—it's powerful and often the right tool for the job.

The Basic Idea: Searching a 1D Array

Let's stick with our analogy of finding a book on a single shelf. The shelf is our array, and the books are the elements. To find a specific book, you start at one end (usually the left, or index 0) and inspect each book until you find the one you want.

In code, this translates to a for loop that visits every index of the array.

Let's say we have an array of high scores from an arcade game and we want to find out if anyone scored exactly 5,000 points.

int[] scores = {1200, 4500, 3250, 5000, 2100};
int targetScore = 5000;

To perform a linear search, we'll:

1. Start at the beginning of the array (index 0).
2. Check if the element at the current index is our targetScore.
3. If it is, we've found it! We can stop searching and report the index where we found it.
4. If it's not, we move to the next index and repeat.
5. If we get all the way to the end of the array and never find it, we can conclude the score isn't in our list.

Here’s what that looks like as a complete method:

/**
 * Searches for a target value in an array of integers.
 * @param arr The array to search through.
 * @param target The value to search for.
 * @return The index of the first occurrence of the target, or -1 if not found.
 */
public int linearSearch(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) {
            return i; // Found it! Return the index and exit the method.
        }
    }
    // If the loop finishes, we never found the target.
    return -1;
}

The "Not Found" Case: A Critical Detail

Look closely at that code. The return -1; statement is outside the for loop.

// AVOID THIS COMMON MISTAKE!
for (int i = 0; i < arr.length; i++) {
    if (arr[i] == target) {
        return i;
    } else {
        return -1; // WRONG!
    }
}

Why is this wrong? This code checks only the first element. If arr[0] isn't the target, it immediately returns -1 and stops, never checking the rest of the array. You can only be sure the item is missing after you've checked every single spot.

Think of it this way: you can't say your friend isn't at the party until you've scanned the whole room. You don't give up after looking at the first person by the door.

Searching from the Other End

The AP standards mention that a linear search can start from either end. To find the last occurrence of a value, or if you have a reason to believe your item is near the end, you can simply reverse the loop:

public int linearSearchFromEnd(int[] arr, int target) {
    for (int i = arr.length - 1; i >= 0; i--) { // Start at the end, go backwards
        if (arr[i] == target) {
            return i; // Found the last (or first from the end) occurrence
        }
    }
    return -1;
}

The logic is identical, just the direction of travel is different.

This also works for ArrayLists, you just use .size() and .get(i) instead of .length and arr[i]. The underlying algorithm is the same.

Stepping It Up: Linear Search on a 2D Array

What if your data isn't a simple list, but a grid? Think of a movie theater seating chart, a spreadsheet, or a bingo card. This is a 2D array.

To search a 2D array, you apply the same linear search logic, but you have to do it for each row. Imagine you're an usher looking for a dropped phone in a theater. You'd likely pick a row, walk down it checking every seat, and if you don't find it, you move to the next row and repeat.

This translates perfectly to a nested loop. The outer loop handles the rows, and the inner loop handles the columns (the seats in that row).

Let's say we have a 2D array representing a grid of lottery numbers, and we want to see if the number 7 is on the ticket.

int[][] lotteryTicket = {
    {23, 4, 19, 42},
    {11, 7, 33, 5},
    {1, 15, 28, 3}
};

Here's how we'd search it:

/**
 * Searches for a target value in a 2D integer array.
 * @param grid The 2D array to search.
 * @param target The value to search for.
 * @return true if the target is found, false otherwise.
 */
public boolean searchGrid(int[][] grid, int target) {
    // Outer loop iterates through each row
    for (int i = 0; i < grid.length; i++) {
        // Inner loop iterates through each element in the current row
        for (int j = 0; j < grid[i].length; j++) {
            if (grid[i][j] == target) {
                return true; // Found it! We can stop immediately.
            }
        }
    }
    // If we get through ALL rows and ALL columns, it's not here.
    return false;
}

Notice here we return a boolean—true or false. This is common for 2D array searches when we just need to know if the item exists. If we needed to know where it was, we might return an array like {i, j} representing the row and column. But for now, a simple "yes" or "no" is perfect.

The core idea is the same: check every spot. For a 2D array, that just means checking every spot in row 0, then every spot in row 1, and so on, until you find your target or run out of spots.

Let's walk through a few examples to make this concrete.

Time to put your knowledge to the test.

1. 1
   Shopping Cart Search

   You have an ArrayList of Product objects from a customer's shopping cart in an e-commerce app. Each Product object has methods getName() (returns a String) and getPrice() (returns a double). Write a method findProductByName(ArrayList<Product> cart, String name) that takes the cart and a product name, and returns the Product object if it's found. If no product with that name is in the cart, it should return null. Hint: Your loop will iterate through the ArrayList. Inside the loop, you'll get the Product at the current index and then use its getName() method to compare with the target name. Remember to use .equals() for comparing Strings!
2. 2
   Game Board Check

   You are given an 8x8 2D char array representing a game board. An empty square is represented by the character '-'. Write a method isBoardFull(char[][] board) that returns true if there are no empty squares left on the board, and false otherwise. Hint: You'll need a nested loop to check every square. What can you do the moment you find the first '-'? Does that give you the final answer right away?