I am grinding LeetCode these days and I encountered the challenge 162. Find Peak Element:
A peak element is an element that is strictly greater than its neighbors.
Given an integer array
nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks.You may imagine that
nums[-1] = nums[n] = -∞.You must write an algorithm that runs in
O(log n)time.Constraints:
1 <= nums.length <= 1000-231 <= nums[i] <= 231 - 1nums[i] != nums[i + 1]for all validi
This question is about using binary search to find a peak element in an array.
I know we can think of the array as alternating ascending and descending sequences. Here is my solution
var findPeakElement = function(nums) {
if(nums.length <= 1) return 0
let left = 0, right = nums.length - 1
while(left <= right) {
const mid = left + right >>> 1
if(nums[mid] > nums[mid + 1]) {
right = mid - 1
} else {
left = mid + 1
}
}
return left === nums.length ? left - 1 : left
};
If the nums[mid] is bigger than the next element in the array that we know we are in the descending sub array and the peak element must be lying in the left, and vice versa if then nums[mid] is smaller than the next element. So far so good. But what confused me is which index I should return eventually - left or right? To figure this out I need to go through a bunch of trial and error.
And if I slightly tweek the question to find the valley element e.g. [1, 3, 20, 4, 1, 0]'s valley elements should be 0. While I can reason about how we narrow the window but I still cannot seem to figure out which index I should return at the end of the binary search.
Here is my attempt for returning the valley element in the array by mirroring what I did for findPeakElement
var findValleyElement = function (nums) {
if (nums.length <= 1) return 0
let left = 0,
right = nums.length - 1
while (left <= right) {
const mid = (left + right) >>> 1
if (nums[mid] > nums[mid + 1]) {
left = mid + 1
} else {
right = mid - 1
}
}
return right
}
But this time I cannot use right as the returned index. I need to use left instead. I cannot seem to think of a consistent way of thinking through this without going through a bunch of examples, which is really not ideal since you still might miss some edge cases.
So my question is, is there some consistent mental model we can adopt when thinking about these binary search problems, specifically which index we should return to satisfy the requirements.
from Binary Search in JS: trying to find a consistent mental model
No comments:
Post a Comment