算法练习(71): 数组的局部最小元素(1.4.18)

本系列博客习题来自《算法(第四版)》，算是本人的读书笔记，如果有人在读这本书的，欢迎大家多多交流。为了方便讨论，本人新建了一个微信群(算法交流)，想要加入的，请添加我的微信号：zhujinhui207407 谢谢。另外，本人的个人博客 http://www.kyson.cn 也在不停的更新中，欢迎一起讨论

算法(第4版)

知识点

• 数组的局部最小元素
• 二分法查找
• 费马

题目

1.4.18 数组的局部最小元素。编写一个程序，给定一个含有 N 个不同整数的数组，找到一个局部最小元素：满足 a[i] < a[i-1]，且 a[i] < a[i+1] 的索引 i。程序在最坏情况下所需的比较次数为 ~ 2lgN。

---

1.4.18 Local minimum of an array. Write a program that, given an array a[] of N distinct integers, finds a local minimum:an index i such that a[i-1] < a[i] < a[i+1]. Your program should use ~2lg N compares in the worst case..
Answer: Examine the middle value a[N/2] and its two neighbors a[N/2 - 1] and a[N/2+1].If a[N/2] is a local minimum, stop; otherwise search in the half with the smaller neighbor.

分析

首先这道题要纠错一下：英文版中有一定错误“an index i such that a[i-1] < a[i] < a[i+1]”，明显有问题，因为要找的是局部最小元素，不是中间数。
接着，继续答题，这道题还有个点需要注意“找到一个局部最小元素”，是的，也就是说不需要找全，只要找到一个即可。这样一来就简单了很多。
最后我们看看英文版的提示：先找到数组的中间数，然后依次往两边查找即可。
需要注意的是，题中给了一个前提，数组的元素互不相同
如果数组的元素不能保证互不相同，不可能在O(lgn)时间内解决这个问题。因为如果这个数组全是1，那么必须要遍历数组中的所有元素才有可能确定不存在，至少是O(n)。
还有一点需要注意，
数组可能为空，或者只有一个元素或者两个元素。当a[i]的前后两个元素都存在时，需要满足“a[i] < a[i-1]，且a[i] < a[i+1]”这个条件，但是如果a[i]是第一个元素或者是最后一个元素，那么只需要看一边。所以对于任何一个数组，”局部最小元素“一定是存在的。

展开来讲，这道题讲的其实是“局部极小值”问题，这个问题在数学届早有研究：

局部最小值：如果存在一个ε>0，使的所有满足|x-x₀| < ε 的x都有f(x₀) ≤ f(x) 我们就把点x₀对应的函数值f(x₀)称为一个函数f的局部最小值。

其实局部最大值/最小值在数学中对应的概念就是极值。

极值：在数学分析中，在给定范围内（相对极值）或函数的整个域（全局或绝对极值），函数的最大值和最小值被统称为极值（极数）。皮埃尔·德·费马（Pierre de Fermat）是第一位提出函数的最大值和最小值的数学家之一。

说到极大值极小值就不得不说到费马这个人。

皮埃尔·德·费马，法国律师和业余数学家。他在数学上的成就不比职业数学家差，他似乎对数论最有兴趣，亦对现代微积分的建立有所贡献。被誉为“业余数学家之王”。

费马最出名的莫过于他的费马大定理：

任何一个整数的立方，不能分成其他另两个数的立方之和；任何一个整数的四次方，也不可能分成为其他另两个数的四次方数之和，更一般来说，不可能将一个高于二次幂的任何整数幂再分成两个其他另两个同次幂数之和。

这个问题麻省理工学院的算法入门课程中也给出了相应的课程，只不过找的是最大值：

1 2 3 4 5 6

如上图，在图4的时候其实已经给出了解决方案，就是“二分法”

答案

public static int localMinimum(int[] x) {
    if (x == null || x.length == 0) {
        return -1;
    }
    if (x.length == 1 || x[0] < x[1]) {
        return 0;
    }
    if (x[x.length - 1] < x[x.length - 2]) {
        return x.length - 1;
    }

    int mid = 0;
    int left = 1;
    int right = x.length - 2;
    while (left < right) {
        mid = (left + right) / 2;
        if (x[mid - 1] < x[mid]) {
            right = mid - 1;
        } else if (x[mid + 1] < x[mid]) {
            left = mid + 1;
        } else {
            return mid;
        }
    }
    return left;
}

测试用例

public static void main(String[] args) {
    int[] a = {2, 1, 3, 4, 5, 6, 11, 14, 8, 25};
    int index = localMinimum(a);
    System.out.println("局部最小元素，" + "a[" + index + "]值为" + a[index]);
}

代码索引

LocalMinimum.java

广告

我的首款个人开发的APP壁纸宝贝上线了，欢迎大家下载。