7.5 Searching

Need to find something in your data? That's what searching is all about! In Java programming, we often need to locate specific items within an ArrayList or array. This guide covers how to search through data step-by-step, focusing on how programmers use loops (iteration) and if-statements (selection) to find what they're looking for.

What is Searching?

Searching is just finding a specific item within a collection of data. Think of it like trying to find a particular book on a bookshelf. In Java, we search through arrays and ArrayLists to:

• Check if a value exists (like seeing if "Harry Potter" is on your bookshelf)
• Find where something is located (which position on the shelf)
• Count how many times something appears
• Find items that meet certain conditions (like all books by a specific author)

Types of Search Algorithms

There are different ways to search, but for this unit, we focus on:

Sequential/Linear Search

Sequential search (also called linear search) is the simplest way to search. It works like this:

1. Start at the beginning
2. Look at each item, one at a time
3. Compare the current item with what you're looking for
4. If you find a match, you're done!
5. If you check everything and don't find a match, the item isn't there

How to Write It in Java for Arrays

public static int linearSearch(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) {
            return i; // Found it! Return the position
        }
    }
    return -1; // Didn't find it, return -1
}

How to Write It in Java for ArrayLists

public static int linearSearch(ArrayList<Integer> list, Integer target) {
    for (int i = 0; i < list.size(); i++) {
        if (list.get(i).equals(target)) {
            return i; // Found it! Return the position
        }
    }
    return -1; // Didn't find it, return -1
}

Using Built-in Methods

Good news! Java's ArrayList already has methods that can search for you:

• indexOf(Object o): Tells you the position of the first match (or -1 if not found)
• contains(Object o): Tells you if the item exists in the list (true or false)

ArrayList<String> names = new ArrayList<>();
names.add("Alice");
names.add("Bob");
names.add("Charlie");

// Using indexOf
int position = names.indexOf("Bob"); // Returns 1 (the second position)

// Using contains
boolean hasAlice = names.contains("Alice"); // Returns true
boolean hasDavid = names.contains("David"); // Returns false

Searching for Objects

When searching for your own custom objects (like Students or Products), you need to:

1. Tell Java how to compare your objects by overriding the equals() method
2. Then you can use the normal search methods

public class Student {
    private String name;
    private int id;
    
    // Constructor and other methods...
    
    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null || getClass() != obj.getClass()) return false;
        Student student = (Student) obj;
        return id == student.id; // We're saying students are the same if they have the same ID
    }
}

// Now you can search for students
ArrayList<Student> students = new ArrayList<>();
// ... add students to the list
Student searchTarget = new Student("Unknown", 12345);
boolean found = students.contains(searchTarget); // Will find any student with ID 12345

Common Search Tasks

Here are typical things you might want to do:

• Find one specific item: Stop as soon as you find a match
• Find all matches: Collect all the matching items in a new list
• Count matches: Keep track of how many matches you find
• Find the biggest/smallest: Keep track of the largest/smallest value you've seen so far

Example: Finding All Matches

public static ArrayList<Integer> findAllMatches(ArrayList<Integer> list, int target) {
    ArrayList<Integer> positions = new ArrayList<>();
    
    for (int i = 0; i < list.size(); i++) {
        if (list.get(i) == target) {
            positions.add(i); // Remember this position
        }
    }
    
    return positions; // Return all the positions where we found matches
}

How Fast Is It?

Sequential search has these characteristics:

• Best case: Super fast if the item is at the beginning
• Worst case: Slow if the item is at the very end or not there at all
• Overall: The time it takes increases directly with the size of your data

Sequential search works well for:

• Smaller collections of data
• Unsorted data
• When you don't search very often

Common Mistakes to Avoid

• Using == with objects: Remember to use .equals() when comparing objects
• Off-by-one errors: Be careful with your loop conditions (use < with length or size())
• Not checking for null: Make sure objects aren't null before using them
• Going out of bounds: Don't try to access positions that don't exist

Summary

Searching is like finding a needle in a haystack - you need a strategy! Sequential search gives us a simple way to find items in our arrays and ArrayLists by checking each element one by one. While not the fastest for huge datasets, it works for all types of data and is straightforward to understand. Mastering search techniques is essential for working with collections of data in your Java programs.