Binary search, template 3

Searching for peaks using binary search algorithm with post-processing and checking left and right neighbors.

by Yurii Predborskyi

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
var findPeakElement = function(nums) {
    if (nums.length === 1) return 0;
    let left = 0, right = nums.length - 1;
    
    while (left + 1 < right) {
        let mid = Math.round((left + right) / 2);
        // for simplicity, take left, mid and right values from array, or use -Infinity if value is outside of nums array length
        let m = nums[mid];
        let l = nums[mid - 1] ? nums[mid - 1] : -Infinity;
        let r = nums[mid + 1] ? nums[mid + 1] : -Infinity;
        if (m > l && m > r) {
            return mid;
        }
        if (r > m) {
            left = mid;
        } else if (l > m) {
            right = mid;
        }
    }
    
    if (nums[right] > nums[left]) {
        if (!nums[right + 1] || nums[right] > nums[right + 1]) {
            return right;
        }
    }
    if (nums[left] > nums[right]) {
        if (!nums[left - 1] || nums[left] > nums[left - 1]) {
            return left;
        }
    }
    // should never happen
    console.log('bad input', nums);
    return -1;
};

let arr = [1,3,2,1];
console.log('expected: 1, calculated:',findPeakElement(arr));

/*
Template 3
Initial Condition: left = 0, right = length-1
Termination: left + 1 == right
Searching Left: right = mid
Searching Right: left = mid
*/