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 any one of the peaks is fine.
You may imagine that num[-1] = num[n] = -∞.
For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.
這道題可以用O(n)直接遍歷一遍苞氮，但是其實(shí)有更好的方法就是binary search。這個(gè)方法看起來(lái)很簡(jiǎn)單但是實(shí)際寫(xiě)的時(shí)候有很多的細(xì)節(jié)需要處理。
其中的一個(gè)就是循環(huán)終止的條件话侧，還有一個(gè)是start蹄溉， end 不恭，mid的賦值哑蔫。
循環(huán)終止的條件原來(lái)想的太簡(jiǎn)單了拂封，以為終究會(huì)有一個(gè)數(shù)字落到
if (nums[mid] > nums[mid-1] && nums[mid] > nums[mid+1] )
{
/* code */
return mid;
}
的條件中案铺。
但是沒(méi)有想到最后只剩倆個(gè)數(shù)怎么辦蔬芥，只剩倆個(gè)數(shù)就會(huì)永遠(yuǎn)陷入死循環(huán)中。沒(méi)有仔細(xì)思考循環(huán)的條件應(yīng)該怎么設(shè)置控汉，導(dǎo)致調(diào)試的時(shí)候浪費(fèi)了很多的時(shí)間笔诵。剛開(kāi)始調(diào)試的時(shí)候不要用太難的case做預(yù)演。用簡(jiǎn)單的case想明白姑子。
第二個(gè)是start和end的賦值乎婿，因?yàn)閙id是已經(jīng)比較過(guò)的數(shù)，所以賦值的時(shí)候要把它去掉街佑。
if ( nums[mid] < nums[mid-1] )
{
/* code */
end = mid - 1;
}
if (nums[mid] > nums[mid-1] )
{
/* code */
start = mid + 1;
}
最后是看別個(gè)的代碼發(fā)現(xiàn)的解決方法谢翎。有一種情況是PeakElement可能是i=0 或者i=n的情況。最開(kāi)始我沒(méi)想到處理的辦法沐旨，但是看了這個(gè)我覺(jué)得這個(gè)辦法不錯(cuò)森逮。
while(start <= end) {
mid = start + (end - start) / 2;
if((mid == 0 || num[mid] >= num[mid - 1]) &&
(mid == n - 1 || num[mid] >= num[mid + 1])) {
return mid;
}else if(mid > 0 && num[mid-1] > num[mid]) {
end = mid - 1;
} else {
start = mid + 1;
}
}
原來(lái)我的代碼是
if (nums[mid] > nums[mid-1] && nums[mid] > nums[mid+1] )
{
/* code */
return mid;
}
他們的寫(xiě)法更簡(jiǎn)潔和完備。
