leetcode Question: Find Peak Element

Practice daily, and train myself to know the algorithms better. Notes from April 8, 2015

"find peak element" question: A peak element is an element that is greater than its neighbors. For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.

So, the websites I read:

1. http://yucoding.blogspot.ca/2014/12/leetcode-question-find-peak-element.html

2. http://www.geeksforgeeks.org/find-a-peak-in-a-given-array/

3. http://courses.csail.mit.edu/6.006/spring11/lectures/lec02.pdf

4. https://leetcode.com/problems/find-peak-element/

5. https://www.youtube.com/watch?v=HtSuA80QTyo  (MIT lecture, 53 minutes, really good one!)

So, I like to write something to help myself ace the question next practice. Using analysis, it may not perform under stress; how about memorization, it will not last after a few months.

Here, using a special case, an array in increasing order. Also, people can help you do analysis if you present a special test case, know where you are in the problem solving.

For example, the array, [1, 2,3,4,5,6,7,8,9], if we go through one by one, 9 is the peak number; but it takes 9 steps from checking 1, then 2, and last is 9. It is not efficient, O(n) steps. So, how to do log(n) step, first one is to check the middle number, 5; and then, 5 is not a peak element, then, analyze and conclude that: [6,7,8,9] has one peak element; and then, check number 8, which is not a peak element; [9] has a perk element. First check is number 5, last check is number 9, only 3 checks; 3 checks is 5, 8, 9.