[C++]LeetCode:118 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 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.
click to show spoilers.
Note:
Your solution should be in logarithmic complexity.
考え方:この問題は二分的に探さなければ、時間の複雑さはO(N)であり、配列を繰り返し、最初の要素を見つける必要があります.それは後続の他の要素より大きく、局所的なピークです.問題では対数時間で検索を完了するように要求されており,二分検索を用いることを考慮している.中間要素が隣接する後続要素より大きい場合、中間要素の左側(中間要素を含む)には必ず局所最大値が含まれ、中間要素が隣接する後続要素より小さい場合、中間要素の右側には必然的に局所最大値が含まれます.最後の左エッジと右エッジが出会うまで、求められたピークを見つけます.
終了条件として左右エッジの出会いを選択し,後続要素mid+1のみと比較し,midが0の場合,mid−1が負の値となる特殊な場合を避けることができる.テーマではnum[-1]=num[n]=負が無限であると仮定するだけで,実際には配列はこの2つの値を得ることができず,ポインタは境界を越える.
ここで、中間要素が隣接する後続要素より大きい場合、中間要素の左側の説明(中間要素を含む)必ず1つの局所最大値を含む.この場合、中間要素もピーク点である可能性があるので、移動するとend=midであり、中間要素end=mid-1を越えることはできない.逆に、中間要素が隣接する後続要素より小さい場合、中間要素の右側は1つの局所最大値を含む.この場合、中間要素は局所最大点ではないに違いない.start= mid + 1.
複雑度:O(lg(n))
AC Code:

class Solution {
public:
    int findPeakElement(const vector &num) {
        if(num.size() == 0) return 0;
        
        int start = 0;
        int end = num.size() - 1;
        
        while(start <= end)
        {
            if(start == end) return start;
            
            int mid = start + (end - start) / 2;
            
            if(num[mid] < num[mid+1])
            {
                start = mid + 1;
            }
            else
            {
                end = mid;
            }
        }
    }
};

二分検索のすべての問題が終わったら、このような問題の特徴と二分検索のすべての応用状況をまとめることができます.