同时获取数组中的最大值和最小值

时间:2021-09-13 15:14:48

找到一个数组中最大值一般用如下方法,首先拿出数组中第一个值作为当前的最大值,然后依次和后面所有的值比较,发现有比当前最大值还大的就更新最大值的记录:

 

同理,最小值也是这么判断:

 

 

 

无论是求最大值还是最小值都进行了n-1次比较,那么同时求最大值是否需要判断2n-2次呢?

 

算法导论第九章给出了一个结论,最多只需要比较3+n-2次比较就可以完成,因为我们可以从数组中一次取两个数据,先将这两个数据进行比较,然后把其中大的与最大值记录比较,小的与最小值记录比较即可,因为取出的两个数据中的小的值不可能还会成为最大值。