Binary Search in JS: trying to find a consistent mental model

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 - 1

nums[i] != nums[i + 1] for all valid i

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.

Solution

When the following condition is true:

if(nums[mid] > nums[mid + 1]) {

...then it could be that mid is a solution, maybe even the only one. So that means you shouldn't exclude it from the range, yet with right = mid - 1 you do exclude it. You should set right = mid. To then avoid a potentially endless loop, the loop condition should be left < right. This will ensure the loop will always end: the range is guaranteed to become smaller in each iteration^*

_{* Let's for instance assume left == right + 1 at a certain moment. Then mid will become equal to left (since the odd bit in the sum is dropped with >>>). Now either we do right = mid or we do left = mid + 1. In either case we get that left == right. In all other cases where left < right, we get a mid that is strictly between those two limits, and then surely the range will become smaller.}

Once the loop exits, left has become equal to right. The only possible index in that range (of 1) is that index.

There is now no more need to check whether left is nums.length, as this cannot happen: with our chosen while condition, left can never become greater than right, ... only equal to it. And since right is a valid index, no such out-of-range check is needed.

Also the case of array size 1 does not need special treatment now.

So:

var findPeakElement = function(nums) {
    let left = 0,
        right = nums.length - 1;

    while (left < right) {
        const mid = (left + right) >>> 1;
        if (nums[mid] > nums[mid + 1]) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }

    return left;
};

Valleys instead of Peaks

Here is my attempt for returning the valley element

If you want to find the valley element, it will not always work unless the following assumption in the question is changed from this:

You may imagine that nums[-1] = nums[n] = -∞

...to this:

You may imagine that nums[-1] = nums[n] = ∞

Once you have that agreed upon, you only have to change the comparison in the above code block from nums[mid] > nums[mid + 1] to nums[mid] < nums[mid + 1].