查找峰元素 · GeeksForGeeks 中文系列教程

# 查找峰元素 > 原文： [https://www.geeksforgeeks.org/find-a-peak-in-a-given-array/](https://www.geeksforgeeks.org/find-a-peak-in-a-given-array/) 给定一个整数数组。在其中找到一个峰元素。如果数组元素不小于其邻居，则它是一个峰。对于角落元素，我们只需要考虑一个邻居。 **示例**： ``` Input: array[]= {5, 10, 20, 15} Output: 20 The element 20 has neighbours 10 and 15, both of them are less than 20. Input: array[] = {10, 20, 15, 2, 23, 90, 67} Output: 20 or 90 The element 20 has neighbours 10 and 15, both of them are less than 20, similarly 90 has neighbous 23 and 67. ``` *在遇到严重问题时，可以更好地解决此问题。* 1. 如果输入数组严格按升序排序，则最后一个元素始终是峰值元素。例如，50 是{10，20，30，40，50}中的峰值元素。 2. 如果输入数组按严格降序排序，则第一个元素始终是峰元素。 100 是{100，80，60，50，20}中的峰值元素。 3. 如果输入数组的所有元素都相同，则每个元素都是峰值元素。从上面的示例可以清楚地看出，输入数组中始终存在一个峰值元素。 **朴素的方法**：可以遍历数组，并且可以返回其邻居小于该元素的元素。 **算法**： 1. 如果在数组中，第一个元素大于第二个元素或最后一个元素大于倒数第二个元素，则打印相应的元素并终止程序。 2. 否则将数组从第二个索引遍历到第二个最后一个索引 3. 如果对于元素 *array [i]* ，它大于其相邻元素，即 *array [i] > array [i-1]和 array [i] > array [i + 1]* ，然后打印该元素并终止。 ``` // A C++ program to find a peak element #include <bits/stdc++.h> using namespace std; // Find the peak element in the array int findPeak(int arr[], int n) { // first or last element is peak element if (n == 1) return arr[0]; if (arr[0] >= arr[1]) return 0; if (arr[n - 1] >= arr[n - 2]) return n - 1; // check for every other element for (int i = 1; i < n - 1; i++) { // check if the neighbors are smaller if (arr[i] >= arr[i - 1] && arr[i] >= arr[i + 1]) return i; } } // Driver Code int main() { int arr[] = { 1, 3, 20, 4, 1, 0 }; int n = sizeof(arr) / sizeof(arr[0]); cout << "Index of a peak point is " << findPeak(arr, n); return 0; } // This code is contributed by Arnab Kundu ``` **输出**： ``` Index of a peak point is 2 ``` **复杂度分析**： * **时间复杂度**：`O(n)`。需要进行一次遍历，因此时间复杂度为`O(n)` * **空间复杂度**：`O(1)`。不需要多余的空间，因此空间复杂度是恒定的 **高效方法**： [分而治之](https://www.geeksforgeeks.org/divide-and-conquer-set-1-find-closest-pair-of-points/)可用于查找 O（Logn）时间的峰值。这个想法是基于二分搜索技术来检查中间元素是否是峰值元素。如果中间元素不是峰值元素，则检查右侧的元素是否大于中间元素，那么右侧总是存在一个峰值元素。如果左侧的元素大于中间的元素，则左侧总是有一个峰值元素。形成递归，峰值元素可以在 log n 个时间内找到。 **Algorithm:** 1. 创建两个变量 *l* 和 *r* ，初始化 *l = 0* 和 *r = n-1* 2. 重复以下步骤，直到 *l < = r* ，下限小于上限 3. 检查中值或索引 *mid =（l + r）/ 2* 是否是峰值元素，如果是，则打印该元素并终止。 4. 否则，如果中间元素左侧的元素更大，则检查左侧的峰值元素，即更新 *r = mid – 1* 5. 否则，如果中间元素右侧的元素较大，则检查右侧的峰元素，即更新 *l =中+ 1* ## C++ ```cpp // A C++ program to find a peak element // using divide and conquer #include <bits/stdc++.h> using namespace std; // A binary search based function // that returns index of a peak element int findPeakUtil(int arr[], int low, int high, int n) { // Find index of middle element // (low + high)/2 int mid = low + (high - low) / 2; // Compare middle element with its // neighbours (if neighbours exist) if ((mid == 0 || arr[mid - 1] <= arr[mid]) && (mid == n - 1 || arr[mid + 1] <= arr[mid])) return mid; // If middle element is not peak and its // left neighbour is greater than it, // then left half must have a peak element else if (mid > 0 && arr[mid - 1] > arr[mid]) return findPeakUtil(arr, low, (mid - 1), n); // If middle element is not peak and its // right neighbour is greater than it, // then right half must have a peak element else return findPeakUtil( arr, (mid + 1), high, n); } // A wrapper over recursive function findPeakUtil() int findPeak(int arr[], int n) { return findPeakUtil(arr, 0, n - 1, n); } // Driver Code int main() { int arr[] = { 1, 3, 20, 4, 1, 0 }; int n = sizeof(arr) / sizeof(arr[0]); cout << "Index of a peak point is " << findPeak(arr, n); return 0; } // This code is contributed by rathbhupendra ``` ## C ``` // C program to find a peak // element using divide and conquer #include <stdio.h> // A binary search based function that // returns index of a peak element int findPeakUtil( int arr[], int low, int high, int n) { // Find index of middle element // (low + high)/2 int mid = low + (high - low) / 2; // Compare middle element with // its neighbours (if neighbours exist) if ((mid == 0 || arr[mid - 1] <= arr[mid]) && (mid == n - 1 || arr[mid + 1] <= arr[mid])) return mid; // If middle element is not peak and // its left neighbour is greater // than it, then left half must have a peak element else if (mid > 0 && arr[mid - 1] > arr[mid]) return findPeakUtil(arr, low, (mid - 1), n); // If middle element is not peak and // its right neighbour is greater // than it, then right half must have a peak element else return findPeakUtil(arr, (mid + 1), high, n); } // A wrapper over recursive function findPeakUtil() int findPeak(int arr[], int n) { return findPeakUtil(arr, 0, n - 1, n); } /* Driver program to check above functions */ int main() { int arr[] = { 1, 3, 20, 4, 1, 0 }; int n = sizeof(arr) / sizeof(arr[0]); printf( "Index of a peak point is %d", findPeak(arr, n)); return 0; } ``` ## Java ```java // A Java program to find a peak // element using divide and conquer import java.util.*; import java.lang.*; import java.io.*; class PeakElement { // A binary search based function // that returns index of a peak element static int findPeakUtil( int arr[], int low, int high, int n) { // Find index of middle element // (low + high)/2 int mid = low + (high - low) / 2; // Compare middle element with its // neighbours (if neighbours exist) if ((mid == 0 || arr[mid - 1] <= arr[mid]) && (mid == n - 1 || arr[mid + 1] <= arr[mid])) return mid; // If middle element is not peak // and its left neighbor is // greater than it, then left half // must have a peak element else if (mid > 0 && arr[mid - 1] > arr[mid]) return findPeakUtil(arr, low, (mid - 1), n); // If middle element is not peak // and its right neighbor // is greater than it, then right // half must have a peak // element else return findPeakUtil( arr, (mid + 1), high, n); } // A wrapper over recursive function // findPeakUtil() static int findPeak(int arr[], int n) { return findPeakUtil(arr, 0, n - 1, n); } // Driver method public static void main(String[] args) { int arr[] = { 1, 3, 20, 4, 1, 0 }; int n = arr.length; System.out.println( "Index of a peak point is " + findPeak(arr, n)); } } ``` ## Python3 ```py # A python 3 program to find a peak # element element using divide and conquer # A binary search based function # that returns index of a peak element def findPeakUtil(arr, low, high, n): # Find index of middle element # (low + high)/2 mid = low + (high - low)/2 mid = int(mid) # Compare middle element with its # neighbours (if neighbours exist) if ((mid == 0 or arr[mid - 1] <= arr[mid]) and (mid == n - 1 or arr[mid + 1] <= arr[mid])): return mid # If middle element is not peak and # its left neighbour is greater # than it, then left half must # have a peak element elif (mid > 0 and arr[mid - 1] > arr[mid]): return findPeakUtil(arr, low, (mid - 1), n) # If middle element is not peak and # its right neighbour is greater # than it, then right half must # have a peak element else: return findPeakUtil(arr, (mid + 1), high, n) # A wrapper over recursive # function findPeakUtil() def findPeak(arr, n): return findPeakUtil(arr, 0, n - 1, n) # Driver code arr = [1, 3, 20, 4, 1, 0] n = len(arr) print("Index of a peak point is", findPeak(arr, n)) # This code is contributed by # Smitha Dinesh Semwal ``` ## C# ```cs // A C# program to find // a peak element element // using divide and conquer using System; class GFG { // A binary search based // function that returns // index of a peak element static int findPeakUtil(int[] arr, int low, int high, int n) { // Find index of // middle element int mid = low + (high - low) / 2; // Compare middle element with // its neighbours (if neighbours // exist) if ((mid == 0 || arr[mid - 1] <= arr[mid]) && (mid == n - 1 || arr[mid + 1] <= arr[mid])) return mid; // If middle element is not // peak and its left neighbor // is greater than it, then // left half must have a // peak element else if (mid > 0 && arr[mid - 1] > arr[mid]) return findPeakUtil(arr, low, (mid - 1), n); // If middle element is not // peak and its right neighbor // is greater than it, then // right half must have a peak // element else return findPeakUtil(arr, (mid + 1), high, n); } // A wrapper over recursive // function findPeakUtil() static int findPeak(int[] arr, int n) { return findPeakUtil(arr, 0, n - 1, n); } // Driver Code static public void Main() { int[] arr = { 1, 3, 20, 4, 1, 0 }; int n = arr.Length; Console.WriteLine("Index of a peak " + "point is " + findPeak(arr, n)); } } // This code is contributed by ajit ``` ## PHP ```php <?php // A PHP program to find a // peak element element using // divide and conquer // A binary search based function // that returns index of a peak // element function findPeakUtil($arr, $low, $high, $n) { // Find index of middle element $mid = $low + ($high - $low) / 2; // (low + high)/2 // Compare middle element with // its neighbours (if neighbours exist) if (($mid == 0 || $arr[$mid - 1] <= $arr[$mid]) && ($mid == $n - 1 || $arr[$mid + 1] <= $arr[$mid])) return $mid; // If middle element is not peak // and its left neighbour is greater // than it, then left half must // have a peak element else if ($mid > 0 && $arr[$mid - 1] > $arr[$mid]) return findPeakUtil($arr, $low, ($mid - 1), $n); // If middle element is not peak // and its right neighbour is // greater than it, then right // half must have a peak element else return(findPeakUtil($arr, ($mid + 1), $high, $n)); } // A wrapper over recursive // function findPeakUtil() function findPeak($arr, $n) { return floor(findPeakUtil($arr, 0, $n - 1, $n)); } // Driver Code $arr = array(1, 3, 20, 4, 1, 0); $n = sizeof($arr); echo "Index of a peak point is ", findPeak($arr, $n); // This code is contributed by ajit ?> ``` **输出**： ``` Index of a peak point is 2 ``` **复杂度分析**： * **时间复杂度**： O（登录）。其中 n 是输入数组中元素的数量。在每一步中，我们的搜索将变成一半。因此可以将其与二分搜索进行比较，因此时间复杂度为`O(log n)` * **空间复杂度**：`O(1)`。不需要额外的空间，因此空间复杂度是恒定的。 **练习**：考虑峰元素的以下修改定义。如果数组元素大于其邻居元素，则它是一个峰。注意，数组可能不包含具有此修改后定义的峰值元素。 **参考**： [http://courses.csail.mit.edu/6.006/spring11/lectures/lec02.pdf](http://courses.csail.mit.edu/6.006/spring11/lectures/lec02.pdf) [http：// www。 youtube.com/watch?v=HtSuA80QTyo](http://www.youtube.com/watch?v=HtSuA80QTyo) ### 询问：[亚马逊](https://practice.geeksforgeeks.org/company/Amazon/) 相关问题： [**查找数组中的局部最小值**](https://www.geeksforgeeks.org/find-local-minima-array/)