Find Peak Element（二分查找）

A peak element is an element that is greater than its neighbors.

Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to anyone of the peaks is fine.

You may imagine that num[-1] = num[n] = -∞.

For example, in array [1, 2, 3, 1], 3 is apeak element and your function should return the index number 2.

click to showspoilers.

Note:

Your solution should be in logarithmic complexity.

Credits:
Special thanks to @ts for adding this problem and creating all testcases.

HideTags

Array Binary Search

注意：

0。。。。。。。。。media1，media2。。。。。。。。n-1

二分的區間是：0。。。。。。。。。media1，media2 和media1，media2。。。。。。。。n-1

若分為0。。。。。。。。。media 和media。。。。。。。。n-1

則media為peak element的情況就被忽略了

另外，頭尾添加負無窮構造新數組時要考慮溢出。

另另外：num.push_back(-2147483647-1);//不能直接push -2147483648 ,若這樣，自動識別-2147483648為無符號的，不能將-號應用於無符號類型

#pragma once
#include
#include
using namespace std;

//取大值
int max(int a, int b)
{
	if (a > b)
		return a;
	return b;
}

int findIt(long long *list, int begain, int end)
{	
	if (end - begain + 1 <= 6)//小到這種程度，遍歷檢查，作為遞歸出口
	{
		for (int i = begain; i <= end - 2; i++)//注意，是end-2
			if (list[i] > list[i + 1])
				continue;
			else
				if (list[i + 1] > list[i + 2])
					return i;//注意，return的不是i+1，因為list中下標都比num中大1
				else
					continue;
		return -1;//for循環結束，為找到，返回-1
	}

	int media1 = (begain + end) / 2;
	int media2 = media1 + 1;//中間兩個元素的下標
	int aheadmedia = (begain + media2) / 2;//前半段中間元素的下標
	int behindmedia = (media1 + end) / 2;//後半段中間元素的下標

	if (list[aheadmedia] > list[begain] && list[aheadmedia] > list[media2])//前半段一定有
		return findIt(list, begain, media2);
	else if (list[behindmedia] > list[media1] && list[behindmedia] > list[end])//前半段沒有，後半段一定有
		return findIt(list, media1, end);
	else//前後都不一定有，但一定有一個有，返回大的，因為沒有的話返回-1
		return max(findIt(list, begain, media2), findIt(list, media1, end));
}


int findPeakElement(const vector &num) 
{
	long long *list = new long long[num.size() + 2];
	//list[0] = num[0] - 1;//模擬頭是負無窮    
	//注意，當num[0]為 - 2147483648時，上面寫法list[0]會變成2147483647，因為num是int型的，會溢出。應下面這樣寫。
	list[0] = num[0];
	list[0]--;
	//注意！！！！！！！若list為int減1後int可能溢出，所以list應為long long類型！！！！long在32位編譯器中也是4位，所以應用long long
	list[num.size() + 1] = num[num.size() - 1];
	list[num.size() + 1]--;//模擬頭是負無窮
	for (int i = 0; i < (int)num.size(); i++)
		list[i + 1] = num[i];
	//至此，頭尾為正無窮的新數組構造完畢

	return findIt(list, 0, num.size() + 1);
}

void main()
{
	vector num;
	num.push_back(-2147483647-1);//不能直接push -2147483648 ,若這樣，自動識別-2147483648為無符號的，不能將-號應用於無符號類型
	cout << "The peak element`s index in num is   " << findPeakElement(num) << endl;
	system("pause");
}