162. 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.

S:binary search

mid可能有四种情况：

1. 处于peak，返回mid
2. 处于升序列中间，返回右边（因为数组末是无限小，右侧先升后降必有peak）
3. 处于降序列中间，同理返回左边
4. 处于谷底，左右都可能出现peak，随意返回

    int findPeakElement(vector<int>& nums) {
      int start = 0;
      int end = nums.size() - 1;
      while (start + 1 < end) {
        int mid = start + (end - start) / 2;
        if (nums[mid] > nums[mid-1] && nums[mid] > nums[mid+1]) {
            return mid;
        }
        else if (nums[mid] > nums[mid-1]) {
          start = mid;
        }
        else {
          end = mid;
        }
      }
      return nums[start] > nums[end]? start: end;
    }

Find Peak Element II

There is an integer matrix which has the following features:

• The numbers in adjacent positions are different.
• The matrix has n rows and m columns.
• For all i < m, A[0][i] < A[1][i] && A[n - 2][i] > A[n - 1][i].
• For all j < n, A[j][0] < A[j][1] && A[j][m - 2] > A[j][m - 1].

We define a position P is a peek if:

A[j][i] > A[j+1][i] && A[j][i] > A[j-1][i] && A[j][i] > A[j][i+1] && A[j][i] > A[j][i-1]

Find a peak element in this matrix. Return the index of the peak.

Notice

The matrix may contains multiple peeks, find any of them.
Example

Given a matrix:

[
  [1 ,2 ,3 ,6 ,5],
  [16,41,23,22,6],
  [15,17,24,21,7],
  [14,18,19,20,10],
  [13,14,11,10,9]
]

return index of 41 (which is[1,1]) or index of 24 (which is[2,2])

S：binary search O(n)

1.找到中间行midR

1. 找到中间行的最大值A[midR][y], 若该最大值比上下元素都大则为peak，否则以比它大的上或下元素为边界，舍去1/2行

2. 在列中重复1，2步, 舍去1/2列

T(n) = O(n) + O(n/2) + T(n/2) = 3/2O(n) + T(n/2) 行二分O(n)+ 列二分O(n/2)

    vector<int> findPeakII(vector<vector<int> > A) {
        int m = A.size();
        if (m < 1) {
            return vector<int>{};
        }
        int n = A[0].size();
        vector<int> result(2);
        int startR = 0, endR = m - 1;
        int startC = 0, endC = n - 1;
        while (1) {  //peak element一定存在，这里不设循环结束条件
            int midR = startR + (endR - startR) / 2;
            int yIdx = startC; 
            for (int i = startC + 1; i <= endC; ++i){
                if (A[midR][i] > A[midR][yIdx]) {
                    yIdx = i;
                }
            }
            if (A[midR - 1][yIdx] < A[midR][yIdx]  && A[midR + 1][yIdx] < A[midR][yIdx]) {
                result[0] = midR;
                result[1] = yIdx;
                return result;
            } else if (A[midR - 1][yIdx] > A[midR][yIdx]) {
                endR = midR - 1;
            } else {
                startR = midR + 1;
            }
            int midC = startC + (endC - startC) / 2;
            int xIdx = startR; 
            for (int i = startR + 1; i <= endR; ++i) {
                if (A[i][midC] > A[xIdx][midC]) {
                    xIdx = i;
                }
            }
            if (A[xIdx][midC - 1] < A[xIdx][midC] && A[xIdx][midC + 1] < A[xIdx][midC]) {
                result[0] = xIdx;
                result[1] = midC;
                return result;
            } else if (A[xIdx][midC - 1] > A[xIdx][midC]) {
                endC = midC - 1;
            } else {
                startC = midC + 1;
            }
        }
    }