跳到主要内容

Java 数组搜索

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

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

基本实现

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是数组的长度。这意味着在最坏情况下,需要检查数组中的所有元素。对于小型数组,这种方法是可以接受的,但对于大型数组,可能会降低效率。

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

基本实现

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数组搜索的几种主要方法:

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

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

7. 练习题

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

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

8. 延伸阅读

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