Find the peak element using BS

Question

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.

class Solution:
# @param num, a list of integer
# @return an integer
def findPeakElement(self, num):
    if len(num)==0: return None
    if len(num)==1: return 0
    return self.findPeakHelper(num,0,len(num)-1)
def findPeakHelper(self,num,start,end):
    mid = (start+end)/2
    if mid>start and mid < end:
        if(num[mid-1]<num[mid] and num[mid]>num[mid+1]):
            return mid
        if(num[mid-1]>num[mid]):
            return self.findPeakHelper(num,start,mid)
        else:
            return self.findPeakHelper(num,mid,end)
    else:
        if num[mid]>num[mid+1]:
            return mid
        else:return mid+1

Answer 1

Your code looks functional. I quite like the idea of splitting the data in halves each time too. There are some things I would do differently, though.

First-up, the 1-liner if statement:

if len(num)==0: return None
if len(num)==1: return 0

also

   else:return mid+1

No, no no ... ;-0 That should be:

if len(num) == 0:
    return None
if len(num) == 1:
    return 0

and

    else:
        return mid + 1

Note that your pasted code is not indented correctly. You indented the class definition, but the class contents are at the same indentation level.

Additionally, I prefer whitespace between method definitions, an empty line.

Actually, I ran your code through a pep8 checker, it pointed out all the compressed-statements too (no whitespace around operators). Here's your code in a format that passes the pep8 check:

class Solution:

    # @param num, a list of integer
    # @return an integer
    def findPeakElement(self, num):
        if len(num) == 0:
            return None
        if len(num) == 1:
            return 0
        return self.findPeakHelper(num, 0, len(num) - 1)

    def findPeakHelper(self, num, start, end):
        mid = (start + end) / 2
        if mid > start and mid < end:
            if(num[mid - 1] < num[mid] and num[mid] > num[mid + 1]):
                return mid
            if(num[mid - 1] > num[mid]):
                return self.findPeakHelper(num, start, mid)
            else:
                return self.findPeakHelper(num, mid, end)
        else:
            if num[mid] > num[mid + 1]:
                return mid
            else:
                return mid + 1

Note:

• spaces surrounding operators
• statements on new line, not the same line as the if/else conditions

Now, about your algorithm...

Really, there's nothing wrong with it, but I believe you can simplify the logic a bit if you treat the mid-point only when needed. Consider the following helper function:

class Solution:

    # @param num, a list of integer
    # @return an integer
    def findPeakElement(self, num):
        if len(num) == 0:
            return None
        if len(num) == 1:
            return 0
        return self.findPeakHelper(num, 0, len(num) - 1)

    def findPeakHelper(self, num, start, end):
        span = end - start
        # span of 1 indicates 2 elements
        if span == 1:
            return start if num[start] > num[end] else end
        mid = start + span / 2
        if num[mid] < num[mid + 1]:
            return self.findPeakHelper(num, mid, end)
        return self.findPeakHelper(num, start, mid)

Note how you don't need the else-statements if the if-statement has a guaranteed return.