查找 Java 中数组元素的索引

在本教程中，我们将了解如何在 Java 中查找数组元素的索引。为避免混淆，我们将假设数组中的所有元素都是唯一的。换句话说，没有元素会出现一次以上。在输入中，我们会得到一个数组和一个数字 k。我们需要找到数组中元素 k 的索引。如果数组中不存在数字 k，则应显示适当的消息。请考虑零索引。

示例 1

输入

int arr[] = {4, 3, 6, 7, 10, 17, 13, 19}, k = 7

输出：元素 7 的索引是 3。

解释：从左边开始，元素 7 的索引是 3。

示例 2

输入

int arr[] = {67, 23, 89, 30, 35, 1, 69, 90, 43, 61}, k = 11

输出：在输入数组中未找到元素 11。

解释：输入数组中不存在元素 11。因此，无法找到其索引。

方法：线性搜索

线性搜索方法很简单。使用循环遍历数组，并检查是否找到元素 k。如果找到，则返回其索引。循环变量此时包含的值就是元素 k 的索引。如果循环结束后仍未找到该元素，则显示适当的消息。

文件名：ArrayElementIndexRecursion.java

输出

For the following array: 
4 3 6 7 10 17 13 19 
The element 7 is found at the index 3


For the following array: 
67 23 89 30 35 1 69 90 43 61 
The element 11 is not found.

复杂度分析：程序的 time complexity 为 O(n)，其中 n 是输入数组中存在的元素总数。程序的 space complexity 为 O(1)，因为程序中没有使用额外的空间。

方法：使用二分搜索

二分搜索方法仅在输入数组按升序或降序排序时有效。在复杂度方面，二分搜索优于线性搜索。

文件名：ArrayElementIndexBinarySearch.java

输出

For the following array: 
4 3 6 7 10 13 17 19 
The element 7 is found at the index 3


For the following array: 
1 23 30 35 43 61 67 69 89 90 
The element 11 is not found.

复杂度分析：程序的 time complexity 为 O(log(n))，其中 n 是输入数组中存在的元素总数。程序的 space complexity 为 O(1)，因为程序中没有使用额外的空间。

方法：使用 Guava 库

Guava 库是由 Google 工程师开发的库。Guava 库提供了各种与原始类型相关的实用程序类，例如 Longs 用于 long、Doubles 用于 double。Ints 用于 int 等。每个实用程序类都有 indexOf() 方法，该方法返回数组中元素第一次出现的位置。

文件名：ArrayElementIndexGuavaLib.java

输出

For the following array:
4 3 6 7 10 17 13 19
The element 7 is found at the index 3


For the following array:
67 23 89 30 35 1 69 90 43 61
The element 11 is not found.

解释：仅当我们将在 guava.jar 文件包含在类路径中时，import 语句才能正常工作。我们已像下面这样编译和运行了该程序。

对于编译过程，我们使用了以下命令

javac -cp ".;/guava.jar" ArrayElementIndexGuavaLib.java

对于运行程序，我们使用了

java -cp ".;/guava.jar" ArrayElementIndexGuavaLib.

可以从 此处 下载 guava.jar 文件。

复杂度分析：程序的 time complexity 为 O(N)，因为 Ints.indexOf 的时间复杂度为 O(N)，其中 N 是数组中存在的元素总数。程序的 space complexity 为 O(1)。

方法：使用 Stream API

Stream 是 Java 8 中引入的新抽象层。在 Stream 中，您可以以声明式方式处理数据，类似于 SQL 语句的处理方式。使用 Stream 包的 IntStream 实用程序，可以找到元素的索引。请参见以下内容。

文件名：ArrayElementIndexStream.java

输出

For the following array:
4 3 6 7 10 17 13 19
The element 7 is found at the index 3


For the following array:
67 23 89 30 35 1 69 90 43 61
The element 11 is not found.

复杂度分析：程序的 time complexity 和 space complexity 与上一个程序相同。

方法：使用 ArrayList

我们可以使用 ArrayList 类的内置方法来实现我们的目标。ArrayList 的 indexOf() 方法非常方便。

文件名：ArrayElementIndexArrayList.java

输出

For the following array:
4 3 6 7 10 17 13 19
The element 7 is found at the index 3


For the following array:
67 23 89 30 35 1 69 90 43 61
The element 11 is not found.

复杂度分析：程序的 time complexity 为 O(N)，因为程序中使用了单个 for 循环。程序的 space complexity 也为 O(N)，因为我们使用 ArrayList 来存储输入数组的元素。N 是输入数组中存在的元素总数。

方法：使用递归

使用递归，也可以找到元素的索引。元素的迭代是通过递归完成的。

文件名：ArrayElementIndexArrayList.java

输出

For the following array:
4 3 6 7 10 17 13 19
The element 7 is found at the index 3


For the following array:
67 23 89 30 35 1 69 90 43 61
The element 11 is not found.

复杂度分析：程序的 time complexity 为 O(N)，因为程序中使用了单个 for 循环。程序的 space complexity 也为 O(N)，因为我们使用 ArrayList 来存储输入数组的元素。N 是输入数组中存在的元素总数。