Java 程序查找数组中的局部最小值

在本节中，我们将讨论数组中的局部最小值是什么以及如何通过 Java 程序找到局部最小值。

数组中的局部最小值是什么？

如果一个数组元素小于其两个邻居（如果存在）元素，则称该元素是数组的局部最小值。对于数组的第一个和最后一个元素，仅考虑一个邻居元素进行比较。请注意，数组中可能存在多个局部最小值，但我们的目标是找到其中一个。

考虑以下示例。

输入： arr[] = {17, 12, 6, 18, 9, 2, 1};

输出： 索引为 2 的元素是局部最小值。

元素 3 是上述数组的局部最小值，因为它小于其两个邻居。在上述数组中，我们观察到有多个局部最小值，它们是 5 和 4。

输入： arr[] = {45, 7, 20, 2, 3};

输出： 索引为 1 的元素是局部最小值。

对于上面的数组，局部最小值是 7，因为它小于其两个元素（右侧和左侧）。

输入： arr[] = {6, 7, 8};

输出： 索引为 0 的元素是局部最小值。

对于上面的数组，局部最小值是 6，因为它小于其右侧的邻居元素。

输入： arr[] = {7, 5, 3};

输出： 索引为 2 的元素是局部最小值。

局部最小值的索引是 2。

对于上面的数组，局部最小值是 3，因为它小于其右侧的元素，并且没有右侧元素。

解决方案

有两种方法

• 朴素方法
• 高效方法

朴素方法

在这种方法中，我们对数组执行线性扫描，一旦找到局部最小值，就返回它。通常，使用 for 循环并将每个元素与其邻居元素进行比较。此方法的复杂度为O(n)。

高效方法

该方法基于二分查找。在此方法中，我们将中间元素与其邻居进行比较。

• 如果数组的中间元素小于其邻居元素，则我们将中间元素作为局部最小值返回。
• 如果数组的中间元素大于其左侧的邻居元素，则数组的左半部分存在局部最小值。
• 如果数组的中间元素大于其右侧的邻居元素，则数组的右半部分存在局部最小值。

上述方法的复杂度为O(log n)。

让我们在 Java 程序中实现上述方法。

LocalMinimaExample.java

输出

Local Minima of the given array is: 3