☕ Java

Java中的搜索算法：详细指南

课程 32 / 37 • 完整阅读理论

Here is the translated HTML article in English, following all your rules. ```html

What is it and why? (a real-life analogy)

Imagine you are standing in front of a huge bookshelf in a library, where thousands of books are arranged in alphabetical order. You need to find the book "The Adventures of Tom Sawyer". How would you search for it?

The first way is the simplest: you start from the first shelf and look through every book in a row until you find the right one. This will take a lot of time, but you definitely won't miss anything. The second way is to open a catalog, find the letter "T", go to the shelf with that letter, and take the book. This is faster, but it requires the books to be sorted.

In programming, search algorithms are the same methods, but for data in a computer. We teach the computer to find an element in an array, list, or other data structure. Why is this necessary? Imagine you are writing an app for searching contacts in a phone, a search engine, or a game where you need to find a character by name. Without search algorithms, the computer will simply iterate through everything, and if there is a lot of data (millions of records), the user will wait forever for a response.

💡 Important: Search algorithms are the foundation upon which databases, search engines (Google, Yandex), and even your favorite games are built. Understanding how they work distinguishes a beginner programmer from a professional.

In this article, we will cover two main search algorithms in Java: linear (sequential) and binary. You will learn how they work, when to use which, and how to avoid common mistakes.

Theory: how it works from the inside

Linear Search

This is the most intuitive algorithm. Imagine you have an array of numbers: [5, 3, 8, 1, 9, 2]. You want to find the number 8. Linear search works like this:

Take the first element (5). Compare it with the target (8). No match.
Take the second element (3). Compare. No match.
Take the third element (8). Compare. Match! Return the index (2).

The algorithm goes through the array from start to end until it finds the desired element. If the element is not found, it returns a special value (usually -1).

Complexity: In the worst case (the element is at the end or doesn't exist), you need to check all N elements. Therefore, the complexity is O(n) (read as "O of n"). This means the search time grows proportionally to the amount of data.

Binary Search

This algorithm only works on sorted data. It uses the "divide and conquer" strategy. Let's go back to the library: if the books are in alphabetical order, you won't check each one — you'll open a book roughly in the middle and see which direction to go next.

How it works on the array [1, 3, 5, 7, 9, 11, 13] when searching for the number 7:

Find the middle of the array. Middle index = (0 + 6) / 2 = 3. The element at index 3 is 7.
Compare 7 with the target 7. Match! Return index 3.

What if we are looking for 11?

Middle = 3, element = 7. 7 < 11, so the target number is to the right.
Now search in the right half: from index 4 to 6. New middle = (4 + 6) / 2 = 5. Element = 11. Found it!

Each step, the algorithm discards half of the array. Therefore, the complexity is O(log n). This is very fast: to find an element among a million records, only 20 steps are needed (because 2^20 ≈ 1,000,000).

⚠️ Critical note: Binary search requires the array to be sorted. If the data is not sorted, binary search will give an incorrect result or won't find the element at all. Sorting is a separate operation that can be costly.

Syntax in Java: all forms and variants

In Java, there are several ways to implement search. We will cover:

Manual implementation (to understand the mechanics)
Using built-in methods from the standard library
Working with different data types (numbers, strings, objects)

Search methods in the Java Collections Framework

Method	Class	Description	Complexity
`Arrays.binarySearch()`	`java.util.Arrays`	Binary search in an array (array must be sorted)	O(log n)
`Collections.binarySearch()`	`java.util.Collections`	Binary search in a list (List, must be sorted)	O(log n)
`ArrayList.contains()`	`java.util.ArrayList`	Checks if the list contains an element (linear search)	O(n)
`HashSet.contains()`	`java.util.HashSet`	Checks if the set contains an element (uses hash table)	O(1) average

Code examples — from simple to complex

Example 1: Linear search in an integer array

public class LinearSearchExample {
    public static void main(String[] args) {
        // Create an array of numbers
        int[] numbers = {10, 23, 45, 67, 89, 12, 34, 56};
        
        // The number we are looking for
        int target = 67;
        
        // Call the linear search method
        int result = linearSearch(numbers, target);
        
        // Check the result
        if (result == -1) {
            System.out.println("Element " + target + " not found in the array.");
        } else {
            System.out.println("Element " + target + " found at index " + result + ".");
        }
    }
    
    // Method for linear search
    public static int linearSearch(int[] arr, int target) {
        // Iterate through the array
        for (int i = 0; i < arr.length; i++) {
            // If the current element matches the target, return its index
            if (arr[i] == target) {
                return i;
            }
        }
        // If the element is not found, return -1
        return -1;
    }
}

Example 2: Binary search (manual implementation)

public class BinarySearchExample {
    public static void main(String[] args) {
        // Sorted array
        int[] sortedNumbers = {2, 5, 8, 12, 16, 23, 38, 45, 56, 72};
        
        int target = 23;
        
        int result = binarySearch(sortedNumbers, target);
        
        if (result == -1) {
            System.out.println("Element " + target + " not found.");
        } else {
            System.out.println("Element " + target + " found at index " + result + ".");
        }
    }
    
    // Binary search method
    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2; // Prevents overflow
            
            // Check if the target is at the middle
            if (arr[mid] == target) {
                return mid;
            }
            
            // If the target is greater, ignore the left half
            if (arr[mid] < target) {
                left = mid + 1;
            }
            // If the target is smaller, ignore the right half
            else {
                right = mid - 1;
            }
        }
        
        // Element not found
        return -1;
    }
}

Example 3: Using built-in methods

import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.ArrayList;

public class BuiltInSearchExample {
    public static void main(String[] args) {
        // ===== Arrays.binarySearch() =====
        int[] numbers = {1, 3, 5, 7, 9, 11, 13};
        int index = Arrays.binarySearch(numbers, 7);
        System.out.println("Index of 7 in array: " + index); // Output: 3
        
        // ===== Collections.binarySearch() =====
        List<String> names = new ArrayList<>();
        names.add("Alice");
        names.add("Bob");
        names.add("Charlie");
        names.add("David");
        Collections.sort(names); // Must be sorted!
        
        int nameIndex = Collections.binarySearch(names, "Charlie");
        System.out.println("Index of Charlie in list: " + nameIndex); // Output: 1
        
        // ===== ArrayList.contains() =====
        List<Integer> numberList = new ArrayList<>();
        numberList.add(10);
        numberList.add(20);
        numberList.add(30);
        
        boolean contains20 = numberList.contains(20);
        System.out.println("List contains 20: " + contains20); // Output: true
    }
}

Example 4: Searching for objects by field

import java.util.Arrays;
import java.util.Comparator;

class Person {
    String name;
    int age;
    
    Person(String name, int age) {
        this.name = name;
        this.age = age;
    }
    
    @Override
    public String toString() {
        return name + " (" + age + " years old)";
    }
}

public class ObjectSearchExample {
    public static void main(String[] args) {
        Person[] people = {
            new Person("Alice", 25),
            new Person("Bob", 30),
            new Person("Charlie", 35),
            new Person("David", 40)
        };
        
        // Sort by age (necessary for binary search)
        Arrays.sort(people, Comparator.comparingInt(p -> p.age));
        
        // Create a key object for searching (only the field we are searching by matters)
        Person key = new Person("", 35); // We are looking for a person aged 35
        int index = Arrays.binarySearch(people, key, Comparator.comparingInt(p -> p.age));
        
        if (index >= 0) {
            System.out.println("Found: " + people[index]);
        } else {
            System.out.println("Person with age 35 not found.");
        }
    }
}

Common mistakes and how to avoid them

Mistake	Consequence	How to fix
Using binary search on an unsorted array	Incorrect result or element not found	Always sort the array first using `Arrays.sort()` or `Collections.sort()`
Forgetting that `binarySearch()` returns a negative value if the element is not found	Using a negative index leads to `ArrayIndexOutOfBoundsException`	Always check the result: `if (index >= 0)`
Using linear search on large datasets	Slow performance (O(n))	If the data can be sorted, use binary search (O(log n))
Not overriding `equals()` and `hashCode()` for custom objects when using `contains()`	`contains()` will use reference comparison and may not find the object	Override `equals()` and `hashCode()` in your class

Conclusion

We have covered two fundamental search algorithms: linear and binary. Linear search is simple and works on any data, but is slow for large volumes. Binary search is lightning fast, but requires sorted data. In real projects, you will often use ready-made methods from Arrays and Collections, but understanding the internal mechanics will help you choose the right tool and avoid mistakes.

Key takeaways:

Linear search — O(n), works on any array/list
Binary search — O(log n), requires sorted data
Use Arrays.binarySearch() for arrays, Collections.binarySearch() for lists
For frequent searches, consider using HashSet or HashMap (O(1) average)
Always check the result of binarySearch() for negative values

Practice writing these algorithms manually, then move on to using built-in tools. This will give you a deep understanding and confidence in your code.

```

← 上一课 Java中的排序算法：详细指南下一步 → Java设计模式：详细指南