162. Find Peak Element

I tried naive way first which runs O(n) time.

1:  class Solution {  
2:  public:  
3:    int findPeakElement(vector<int>& nums) {  
4:      int peak = nums.size()-1;  
5:      for (int i = 0; i < nums.size()-1; i++) {  
6:        if (nums[i] > nums[i+1]) {  
7:          peak = i;  
8:          break;  
9:        }  
10:      }  
11:      return peak;  
12:    }  
13:  };  

Obviously, this naive way isn’t the best. We can do it by binary search. The idea is we keep looking for the two numbers in the middle. And if left middle number is less than the right middle number, we point left pointer to the right middle number, otherwise, we point right pointer to the left middle number. In this way, left and right pointers are always pointing to the larger one which will eventually help us find the peak.

1:  class Solution {  
2:  public:  
3:    int findPeakElement(vector<int>& nums) {  
4:      int l = 0, r = nums.size()-1;  
5:      while (l < r) {  
6:        int mid1 = l + (r - l) / 2;  
7:        int mid2 = mid1 + 1;  
8:        if (nums[mid1] < nums[mid2]) {  
9:          l = mid2;  
10:        } else {  
11:          r = mid1;  
12:        }  
13:      }  
14:      return l;  
15:    }  
16:  };