# 查找峰元素 > 原文： [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/)