Java 数组搜索

在Java编程中，数组搜索是一项基础且重要的操作。无论是查找特定元素、确认元素是否存在，还是寻找满足特定条件的元素，高效的搜索算法都能帮助我们快速完成任务。本文将介绍Java中常用的数组搜索方法，并通过实例展示它们的应用。

1. 线性搜索（Linear Search）

线性搜索是最简单的搜索方法，它从头到尾遍历数组的每个元素，直到找到目标元素或遍历完整个数组。

基本实现

public static int linearSearch(int[] arr, int key) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == key) {
            return i; // 返回找到元素的索引
        }
    }
    return -1; // 未找到元素返回-1
}

使用示例

public class LinearSearchExample {
    public static void main(String[] args) {
        int[] numbers = {10, 20, 30, 40, 50};
        int target = 30;
        
        int result = linearSearch(numbers, target);
        
        if (result != -1) {
            System.out.println("元素 " + target + " 在索引 " + result + " 处找到");
        } else {
            System.out.println("元素 " + target + " 未在数组中找到");
        }
    }
    
    public static int linearSearch(int[] arr, int key) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == key) {
                return i;
            }
        }
        return -1;
    }
}

输出：

元素 30 在索引 2 处找到

备注

线性搜索的时间复杂度为O(n)，其中n是数组的长度。这意味着在最坏情况下，需要检查数组中的所有元素。对于小型数组，这种方法是可以接受的，但对于大型数组，可能会降低效率。

2. 二分搜索（Binary Search）

二分搜索是一种更高效的搜索算法，但要求数组必须是已排序的。它通过将搜索范围反复减半来快速定位目标元素。

基本实现

public static int binarySearch(int[] arr, int key) {
    int left = 0;
    int right = arr.length - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        // 检查mid位置的元素
        if (arr[mid] == key) {
            return mid; // 找到目标元素
        }
        
        // 如果key大于mid位置的元素，搜索右侧
        if (arr[mid] < key) {
            left = mid + 1;
        }
        // 如果key小于mid位置的元素，搜索左侧
        else {
            right = mid - 1;
        }
    }
    
    return -1; // 未找到元素
}

使用示例

public class BinarySearchExample {
    public static void main(String[] args) {
        // 注意：数组必须是已排序的
        int[] numbers = {10, 20, 30, 40, 50, 60, 70};
        int target = 40;
        
        int result = binarySearch(numbers, target);
        
        if (result != -1) {
            System.out.println("元素 " + target + " 在索引 " + result + " 处找到");
        } else {
            System.out.println("元素 " + target + " 未在数组中找到");
        }
    }
    
    public static int binarySearch(int[] arr, int key) {
        int left = 0;
        int right = arr.length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (arr[mid] == key) {
                return mid;
            }
            
            if (arr[mid] < key) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return -1;
    }
}

输出：

元素 40 在索引 3 处找到

提示

二分搜索的时间复杂度为O(log n)，这使它在处理大型排序数组时非常高效。然而，如果数组未排序，则需要先对数组进行排序(时间复杂度O(n log n))，再使用二分搜索。

3. 使用Arrays.binarySearch()

Java的Arrays类提供了内置的二分搜索方法，可以直接用于已排序的数组。

基本用法

import java.util.Arrays;

public class ArraysBinarySearchExample {
    public static void main(String[] args) {
        int[] numbers = {10, 20, 30, 40, 50, 60, 70};
        int target = 40;
        
        int result = Arrays.binarySearch(numbers, target);
        
        if (result >= 0) {
            System.out.println("元素 " + target + " 在索引 " + result + " 处找到");
        } else {
            System.out.println("元素 " + target + " 未在数组中找到");
        }
    }
}

输出：

元素 40 在索引 3 处找到

警告

使用Arrays.binarySearch()方法时，如果数组未排序，结果将是不确定的。此外，如果未找到元素，该方法返回的是-(插入点)-1，而不是简单的-1。插入点是指该元素应该插入到数组中的位置，以维持数组的有序性。

搜索对象数组

对于对象数组，可以使用重载的binarySearch方法，提供一个比较器来定义对象的排序规则。

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

public class ObjectArraySearchExample {
    public static void main(String[] args) {
        Person[] people = {
            new Person("Alice", 25),
            new Person("Bob", 30),
            new Person("Charlie", 20),
            new Person("David", 35)
        };
        
        // 按年龄排序
        Arrays.sort(people, Comparator.comparingInt(Person::getAge));
        
        // 查找年龄为30的人
        Person target = new Person("Unknown", 30);
        int result = Arrays.binarySearch(people, target, Comparator.comparingInt(Person::getAge));
        
        if (result >= 0) {
            System.out.println("找到年龄为30的人: " + people[result].getName());
        } else {
            System.out.println("未找到年龄为30的人");
        }
    }
    
    static class Person {
        private String name;
        private int age;
        
        public Person(String name, int age) {
            this.name = name;
            this.age = age;
        }
        
        public String getName() {
            return name;
        }
        
        public int getAge() {
            return age;
        }
    }
}

输出：

找到年龄为30的人: Bob

4. 搜索多维数组

对于多维数组，我们可以通过嵌套循环来实现搜索。

public class MultiDimensionalArraySearchExample {
    public static void main(String[] args) {
        int[][] matrix = {
            {10, 20, 30},
            {40, 50, 60},
            {70, 80, 90}
        };
        
        int target = 50;
        int[] result = searchInMatrix(matrix, target);
        
        if (result != null) {
            System.out.println("元素 " + target + " 在位置 [" + result[0] + "][" + result[1] + "] 处找到");
        } else {
            System.out.println("元素 " + target + " 未在矩阵中找到");
        }
    }
    
    public static int[] searchInMatrix(int[][] matrix, int target) {
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if (matrix[i][j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return null;
    }
}

输出：

元素 50 在位置 [1][1] 处找到

5. 实际应用场景

学生成绩查询系统

以下是一个简单的学生成绩查询系统，展示了数组搜索在实际应用中的用法：

import java.util.Arrays;
import java.util.Scanner;

public class StudentGradeSystem {
    public static void main(String[] args) {
        Student[] students = {
            new Student(1001, "张三", 85),
            new Student(1002, "李四", 92),
            new Student(1003, "王五", 78),
            new Student(1004, "赵六", 90),
            new Student(1005, "钱七", 65)
        };
        
        // 按学号排序
        Arrays.sort(students, (s1, s2) -> Integer.compare(s1.getId(), s2.getId()));
        
        Scanner scanner = new Scanner(System.in);
        System.out.print("请输入要查询的学生学号: ");
        int searchId = scanner.nextInt();
        
        // 创建一个临时Student对象用于搜索
        Student key = new Student(searchId, "", 0);
        
        int index = Arrays.binarySearch(students, key, 
            (s1, s2) -> Integer.compare(s1.getId(), s2.getId()));
        
        if (index >= 0) {
            Student found = students[index];
            System.out.println("找到学生: " + found.getName() + 
                ", 学号: " + found.getId() + ", 成绩: " + found.getGrade());
        } else {
            System.out.println("未找到学号为 " + searchId + " 的学生");
        }
        
        scanner.close();
    }
    
    static class Student {
        private int id;
        private String name;
        private int grade;
        
        public Student(int id, String name, int grade) {
            this.id = id;
            this.name = name;
            this.grade = grade;
        }
        
        public int getId() {
            return id;
        }
        
        public String getName() {
            return name;
        }
        
        public int getGrade() {
            return grade;
        }
    }
}

输入与输出示例：

请输入要查询的学生学号: 1003
找到学生: 王五, 学号: 1003, 成绩: 78

电话簿应用

这是一个简单的电话簿应用，展示了如何在已排序的联系人数组中搜索：

import java.util.Arrays;
import java.util.Scanner;

public class PhoneBookApp {
    public static void main(String[] args) {
        Contact[] phoneBook = {
            new Contact("张三", "13812345678"),
            new Contact("李四", "13987654321"),
            new Contact("王五", "13700001111"),
            new Contact("赵六", "13922223333"),
            new Contact("钱七", "13944445555")
        };
        
        // 按名字排序
        Arrays.sort(phoneBook, (c1, c2) -> c1.getName().compareTo(c2.getName()));
        
        Scanner scanner = new Scanner(System.in);
        System.out.print("请输入要查找的联系人姓名: ");
        String searchName = scanner.nextLine();
        
        // 使用线性搜索
        int index = linearSearch(phoneBook, searchName);
        
        if (index != -1) {
            Contact found = phoneBook[index];
            System.out.println("找到联系人: " + found.getName() + 
                ", 电话: " + found.getPhoneNumber());
        } else {
            System.out.println("未找到联系人: " + searchName);
        }
        
        scanner.close();
    }
    
    public static int linearSearch(Contact[] contacts, String name) {
        for (int i = 0; i < contacts.length; i++) {
            if (contacts[i].getName().equals(name)) {
                return i;
            }
        }
        return -1;
    }
    
    static class Contact {
        private String name;
        private String phoneNumber;
        
        public Contact(String name, String phoneNumber) {
            this.name = name;
            this.phoneNumber = phoneNumber;
        }
        
        public String getName() {
            return name;
        }
        
        public String getPhoneNumber() {
            return phoneNumber;
        }
    }
}

输入与输出示例：

请输入要查找的联系人姓名: 王五
找到联系人: 王五, 电话: 13700001111

6. 总结

在本文中，我们学习了Java数组搜索的几种主要方法：

1. 线性搜索：简单直接，适用于任何数组，但对于大型数组效率较低。
2. 二分搜索：高效但要求数组已排序，时间复杂度为O(log n)。
3. Arrays.binarySearch()：Java内置的二分搜索方法，适用于已排序的数组。
4. 多维数组的搜索：通过嵌套循环实现。

数组搜索是编程中的基础操作，掌握这些搜索技术将帮助您编写更高效的代码。在实际应用中，根据具体情况选择合适的搜索方法至关重要。

7. 练习题

为了巩固所学知识，尝试完成以下练习：

1. 实现一个方法，在一个整数数组中找出所有出现次数超过数组长度一半的元素。
2. 编写一个程序，在二维数组中查找给定值，并返回其位置（行和列）。
3. 修改线性搜索算法，使其能够处理包含重复元素的数组，并返回所有匹配元素的索引。
4. 实现一个简单的图书管理系统，能够通过书名或作者名搜索图书。
5. 对比线性搜索和二分搜索在不同数组大小下的性能差异。

8. 延伸阅读

• Java Arrays类的官方文档
• 更多排序和搜索算法
• 算法复杂度分析

通过理解和应用这些搜索方法，你将能够在处理数组数据时做出更明智的选择，并编写更加高效的Java程序。