极客笔记C++程序 在数组中查找最小和最大元素
C++作为一门高效性能的语言，经常被用于处理大规模的数据。在实际开发中，如何对数组进行高效的查找是一个非常重要的问题。本文将详细介绍如何在C++中实现在数组中查找最小和最大元素。
1. 暴力枚举法
暴力枚举法是最简单、也是最容易想到的一种方法。它的原理很简单，从数组的第一个位置开始，依次遍历整个数组，每次找到一个数字就和当前的最大值和最小值进行比较，如果大于最大值，则将其更新为最大值；如果小于最小值，则将其更新为最小值。
以下是使用暴力枚举法查找最大值和最小值的示例代码：
#include<iostream>
using namespace std;
void findMinMax(int arr[],int n,int& min,int& max){
min=max=arr[0];
for(int i=1;i<n;i++){
if(arr[i]>max) max=arr[i];
if(arr[i]<min) min=arr[i];
}
}
int main(){
int arr[]={11,4,7,8,1,9,2,5,3,10};
int n=sizeof(arr)/sizeof(arr[0]);
int min,max;
findMinMax(arr,n,min,max);
cout<<"The minimum element of array is : "<<min<<endl;
cout<<"The maximum element of array is : "<<max<<endl;
return 0;
}
上述代码中，findMinMax函数接受一个整型数组arr、数组长度n以及两个引用类型变量min和max作为参数，用于返回最小值和最大值。在函数内部，我们首先初始化最小值和最大值为数组第一个元素，然后从数组第二个元素开始遍历整个数组，每次将当前元素与最大值、最小值进行比较，如果大于最大值，则将其更新为最大值；如果小于最小值，则将其更新为最小值。最终，函数返回最小值和最大值。
下面是上述代码的输出结果：
The minimum element of array is : 1
The maximum element of array is : 11
暴力枚举法看起来非常容易实现，但是其时间复杂度为O(n)，即需要遍历整个数组，因此在大规模数据的情况下，它的效率并不高。
2. 分治法
分治法是一种高效的算法，它将一个大问题分成若干个小问题，再对每个小问题进行求解，最终将每个小问题的解合并成一个整体的解。在这个问题中，我们可以将一个大数组分成两个小数组，分别求解最小值和最大值，然后将两个小数组的解合并起来，得到整个数组的最大值和最小值。
以下是使用分治法查找最大值和最小值的示例代码：
#include<iostream>
using namespace std;
struct result{
int max,min;
};
result findMinMax(int arr[], int low, int high){
result res;
if(low==high){ // 数组中只有一个元素
res.max=res.min=arr[low];
return res;
}
else if(high-low==1){ // 数组中有两个元素
if(arr[low]>arr[high]){
res.max=arr[low];
res.min=arr[high];
}
else{
res.max=arr[high];
res.min=arr[low];
}
return res;
}
else{ // 数组中有多个元素
int mid=(low+high)/2;
result leftRes=findMinMax(arr,low,mid); // 递归处理左半部分
result rightRes=findMinMax(arr,mid+1,high); // 递归处理右半部分
if(leftRes.min<rightRes.min) res.min=leftRes.min;
else res.min=rightRes.min;
if(leftRes.max>rightRes.max) res.max=leftRes.max;
else res.max=rightRes.max;
return res;
}
}
int main(){
int arr[]={11,4,7,8,1,9,2,5,3,10};
int n=sizeof(arr)/sizeof(arr[0]);
result res=findMinMax(arr,0,n-1);
cout<<"The minimum element of array is : "<<res.min<<endl;
cout<<"The maximum element of array is : "<<res.max<<endl;
return 0;
}
上面代码中，findMinMax函数同样接受一个整型数组arr、左右指针low和high作为参数，用于返回最小值和最大值。在函数内部，我们首先针对不同情况（只有一个元素、两个元素、多个元素）进行求解，当数组中只有一个元素时，最大值和最小值均为该元素；当数组中有两个元素时，比较这两个元素的大小，得到最大值和最小值；当数组中有多个元素时，分治遍历数组，分别求解左半部分和右半部分的最小值和最大值，在合并两部分的结果时，比较出左半部分的最小值和右半部分的最小值中较小的一个，以及左半部分的最大值和右半部分的最大值中较大的一个，最终即可得到整个数组的最小值和最大值。
下面是上述代码的输出结果：
The minimum element of array is : 1
The maximum element of array is : 11
分治法的时间复杂度为O(nlogn)，因此它的效率远高于暴力枚举法。但是在分治算法的过程中，会有较多的递归调用，导致程序的栈空间不断增大，如果要应对大规模的数据，可能会有栈溢出的风险。
3. STL库函数
STL库中提供了一些非常方便的函数，可以帮助我们快速地查找数组中的最小值和最大值。其中，用于查找最小值的函数是min_element，用于查找最大值的函数是max_element。
以下是使用STL库函数查找最大值和最小值的示例代码：
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
int arr[]={11,4,7,8,1,9,2,5,3,10};
int n=sizeof(arr)/sizeof(arr[0]);
// 查找最小值
int* minPtr=min_element(arr,arr+n);
cout<<"The minimum element of array is : "<<*minPtr<<endl;
// 查找最大值
int* maxPtr=max_element(arr,arr+n);
cout<<"The maximum element of array is : "<<*maxPtr<<endl;
return 0;
}
在上述代码中，我们首先定义一个整型数组arr，并计算出其长度n。然后，我们使用min_element函数查找最小值，该函数接受一个迭代器指向数组的第一个元素和最后一个元素的下一个位置。函数返回一个指向该元素的指针，最后输出即可。对于max_element函数的使用，也类似。
下面是上述代码的输出结果：
The minimum element of array is : 1
The maximum element of array is : 11
可以看到，STL库函数具有非常高的效率和方便性，推荐在实际开发中使用。
结论
本文介绍了在C++中实现在数组中查找最小和最大元素的三种方法，它们分别是暴力枚举法、分治法和STL库函数。这三种方法各有优缺点，暴力枚举法虽然简单但效率不高，适用于小规模的数据；分治法时间复杂度低，适用于大规模的数据，但需要注意栈溢出；而STL库函数方便高效，推荐在实际开发中使用。对于不同场景下的需求，我们可以根据实际情况选择合适的方法。