LeetCode: Find Peak Element

Initial codes:
Use three pointers to track three adjacent numbers.
Note: write sudo codes for logics first.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

class Solution { public: int findPeakElement(vector<int>& nums) { int left, cur, right; left = -1; cur=0; right=1; //for(int cur=0; cur<nums.size(); cur++){ while(cur<nums.size()){ // if cur < left l, c, r ++ if(left < 0 || nums[left] > nums[cur]){ left++; cur++; right++; continue; } // if cur > left, if cur > right, return cur // if cur < right, l, c, r ++ if(right >= nums.size() || nums[cur] > nums[right]) return cur; else{ left++; cur++; right++; } } } };

Analysis:
worst case: complexity O(n)
The codes can be simplified to just find the first element which is smaller than its adjacent front element.

1 2 3 4 5 6 7 8 9

class Solution { public: int findPeakElement(vector<int>& nums) { for(int i=1; i<nums.size(); i++){ if(nums[i-1] > nums[i]) return i-1; } return nums.size()-1; } };

Optimization: binary search
 O(log n)
Recursive:

1 2 3 4 5 6 7 8 9 10 11 12

class Solution { public: int bs(int left, int right, vector<int>& nums){ if(left == right) return left; int mid = (left + right) / 2; if( nums[mid] > nums[mid + 1]) return bs(left, mid, nums); if( nums[mid] < nums[mid + 1]) return bs(mid+1, right, nums); } int findPeakElement(vector<int>& nums) { return bs(0, nums.size()-1, nums); } };

While loop:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

class Solution { public: int findPeakElement(vector<int>& nums) { int left = 0; int right = nums.size()-1; while(left <= right){ if(left == right) return left; int mid = (left + right)/2; if( nums[mid] > nums[mid + 1]) { right = mid; }else{ left = mid + 1; } } } };

Reference:
http://blog.csdn.net/u010367506/article/details/41943309