1 題目

??尋找峰值（Find Peak Element）

lintcode：題號——75，難度——medium

2 描述

??給定一個整數數組(size為n)，其具有以下特點：相鄰位置的數字是不同的；A[0] < A[1] 并且 A[n - 2] > A[n - 1]；假定P是峰值的位置則滿足A[P] > A[P-1]且A[P] > A[P+1]，返回數組中任意一個峰值的位置。數組保證至少存在一個峰；如果數組存在多個峰，返回其中任意一個就行；數組至少包含 3 個數。

??樣例1：

輸入：A = [1, 2, 1, 3, 4, 5, 7, 6]
輸出：1
解釋：

返回任意一個峰頂元素的下標，元素2的下標為1，下標6也同樣正確。

??樣例2：

輸入：A = [1,2,3,4,1]
輸出：3
解釋：

返回峰頂元素4的下標3。

3 思路

??尋找峰值點，峰值點的特征是點的左邊處于遞增狀態、右邊處于遞減狀態。題中對數組做了一些限定：A[0] < A[1]，即起點是遞增狀態； A[n - 2] > A[n - 1]，即到達終點時候是遞減狀態，且相鄰位置的數字不同。需要找到數組中的任意一個峰值即可，可以通過遞增遞減的狀態來尋找，即在任意一個區間中，如果起點遞增、終點遞減，那這個區間內一定有峰值，通過二分法拆分為“half half”的方式，每次留下一定存在峰值的區間，拋掉不一定存在峰值的區間，最后即可找到。

1. 取中點；
2. 比較中點與下一個點，判斷當前處于遞增還是遞減；
3. 找到起點遞增、終點遞減這樣的一定存在峰值的區間，拋掉另一半不一定存在峰值的區間。
4. 重復上述過程，直到找到峰值。

3.1 圖解

輸入：A = [1, 2, 1, 3, 4, 5, 7, 6]
輸出：6
解釋：

返回任意一個峰頂元素的下標即可，峰值元素7的下標為6。

3.2 時間復雜度

??算法的時間復雜度為O(log n)。

3.3 空間復雜度

??算法的空間復雜度為O(1)。

4 源碼

??注意事項：

1. 最后兩個元素中取峰值的時候，在邏輯上可以直接取end。

因為在最后一次縮小區間的時候，必定是end = mid的情況。如果最后一次縮小區間是start = mid的情況，則說明在縮小后的區間內start點還是處于遞增的狀態，start必定還不是峰值，區間還能再縮。

2. 返回的是序號，不是元素值。

??C++版本：

/**
* @param A: 整數數組
* @return: 任意峰值點的下標序號
*/
int findPeak(vector<int> &A) {
	// write your code here
	if (A.size() < 3)
	{
		return -1;
	}

	int start = 0;
	int end = A.size() - 1;
	int mid = 0;
	while (start + 1 < end)
	{
		mid = start + (end - start) / 2;
		if (A.at(mid) < A.at(mid + 1))
		{
			start = mid;
		}
		if (A.at(mid) > A.at(mid + 1))
		{
			end = mid;
		}
	}

        return end;
}