Fork me on GitHub

Find Peak Element

Posted on

Linkage

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

Naive Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int findPeakElement(int[] nums) {
        int length = nums.length;
        if (length == 0) return -1;
        if (length == 1) return 0;
        
        int left = 0, right = length-1;
        int middle = (left + right) / 2;
        long leftItem, rightItem, currentItem;
        while (left <= right) {
            currentItem = nums[middle];
            leftItem = middle - 1 < 0 ? (long) Double.NEGATIVE_INFINITY : nums[middle - 1];
            rightItem = middle + 1 > length-1 ? (long) Double.NEGATIVE_INFINITY : nums[middle + 1];
            if (currentItem > leftItem && currentItem > rightItem) return middle;
            if (currentItem <= leftItem) 
                right = middle - 1;
            else
                left = middle + 1;
            middle = (left + right) / 2;
        }
        return -1;
    }
}

Log N Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int findPeakElement(int[] nums) {
        int length = nums.length;
        if (length == 0) return -1;
        if (length == 1) return 0;
        
        int left = 0, right = length-1;
        int middle = (left + right) / 2;
        long leftItem, rightItem, currentItem;
        while (left <= right) {
            currentItem = nums[middle];
            leftItem = middle - 1 < 0 ? (long) Double.NEGATIVE_INFINITY : nums[middle - 1];
            rightItem = middle + 1 > length-1 ? (long) Double.NEGATIVE_INFINITY : nums[middle + 1];
            if (currentItem > leftItem && currentItem > rightItem) return middle;
            if (currentItem <= leftItem) 
                right = middle - 1;
            else
                left = middle + 1;
            middle = (left + right) / 2;
        }
        return -1;
    }
}