Java 数组搜索
在Java编程中，数组搜索是一项基础且重要的操作。无论是查找特定元素、确认元素是否存在，还是寻找满足特定条件的元素，高效的搜索算法都能帮助我们快速完成任务。本文将介绍Java中常用的数组搜索方法，并通过实例展示它们的应用。
1. 线性搜索（Linear Search）
线性搜索是最简单的搜索方法，它从头到尾遍历数组的每个元素，直到找到目标元素或遍历完整个数组。
基本实现
java
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
}
使用示例
java
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）
二分搜索是一种更高效的搜索算法，但要求数组必须是已排序的。它通过将搜索范围反复减半来快速定位目标元素。
基本实现
java
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; // 未找到元素
}
使用示例
java
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类提供了内置的二分搜索方法，可以直接用于已排序的数组。
基本用法
java
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方法，提供一个比较器来定义对象的排序规则。
java
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. 搜索多维数组
对于多维数组，我们可以通过嵌套循环来实现搜索。
java
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. 实际应用场景
学生成绩查询系统
以下是一个简单的学生成绩查询系统，展示了数组搜索在实际应用中的用法：
java
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
电话簿应用
这是一个简单的电话簿应用，展示了如何在已排序的联系人数组中搜索：
java
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数组搜索的几种主要方法：
- 线性搜索：简单直接，适用于任何数组，但对于大型数组效率较低。
- 二分搜索：高效但要求数组已排序，时间复杂度为O(log n)。
- Arrays.binarySearch()：Java内置的二分搜索方法，适用于已排序的数组。
- 多维数组的搜索：通过嵌套循环实现。
数组搜索是编程中的基础操作，掌握这些搜索技术将帮助您编写更高效的代码。在实际应用中，根据具体情况选择合适的搜索方法至关重要。
7. 练习题
为了巩固所学知识，尝试完成以下练习：
- 实现一个方法，在一个整数数组中找出所有出现次数超过数组长度一半的元素。
- 编写一个程序，在二维数组中查找给定值，并返回其位置（行和列）。
- 修改线性搜索算法，使其能够处理包含重复元素的数组，并返回所有匹配元素的索引。
- 实现一个简单的图书管理系统，能够通过书名或作者名搜索图书。
- 对比线性搜索和二分搜索在不同数组大小下的性能差异。
8. 延伸阅读
通过理解和应用这些搜索方法，你将能够在处理数组数据时做出更明智的选择，并编写更加高效的Java程序。