javascript - JS 中的二进制搜索 : trying to find a consistent mental model

Question

这几天在磨 LeetCode，遇到了挑战 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

这道题是关于使用二分法查找数组中的峰值元素。

我知道我们可以将数组视为交替的升序和降序序列。这是我的解决方案

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
};

如果 nums[mid]大于数组中的下一个元素，我们知道我们在降序子数组中，并且峰值元素必须位于左侧，反之亦然，如果那时 nums[mid]小于下一个元素。到目前为止，一切都很好。但令我困惑的是我最终应该返回哪个索引 - left或 right ?为了弄清楚这一点，我需要经历大量的试验和错误。

如果我稍微调整一下问题以找到 山谷元素，例如[1, 3, 20, 4, 1, 0]的山谷元素应该是 0 .虽然我可以推断我们如何缩小窗口，但我似乎仍然无法确定在二分搜索结束时应该返回哪个索引。

这是我尝试通过镜像我对 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
}

但是这次我不能使用 right作为返回的索引。我需要使用 left反而。如果不通过一堆示例，我似乎无法想到一种一致的思考方式，这确实不理想，因为您仍然可能会错过一些边缘情况。

所以我的问题是，在考虑这些二分搜索问题时，我们是否可以采用一些一致的心智模型，特别是我们应该返回哪个索引来满足要求。

Answer 1

当下列条件为真时:

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

...那么它可能是mid是一个解决方案，甚至可能是唯一的一个。所以这意味着你不应该将它排除在范围之外，但是 right = mid - 1你确实排除了它。您应该设置 right = mid .为了避免潜在的无限循环，循环条件应该是 left < right .这将确保循环始终结束:保证范围在每次迭代中变小^*

_{* 例如假设 left == right + 1在某个时刻。那么mid将等于 left (因为总和中的奇数位被 >>> 丢弃)。现在我们要么做right = mid或者我们做 left = mid + 1 .无论哪种情况，我们都会得到 left == right .在所有其他情况下，left < right , 我们得到一个 mid即严格在这两个限制之间，那么范围肯定会变小。}

一旦循环退出，left已经等于 right .该范围内(1 个)中唯一可能的索引是 that 索引。

现在不再需要检查 left是 nums.length ，因为这不可能发生:使用我们选择的 while条件，left永远不能大于 right , ... 只等于它。自从right是一个有效的索引，不需要这种超出范围的检查。

数组大小为1的情况现在也不需要特殊处理了。

所以:

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;
};

山谷而不是山峰

Here is my attempt for returning the valley element

如果您想找到 valley 元素，它并不总是有效除非问题中的以下假设从此改变:

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

...到这个:

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

一旦达成一致，您只需将上述代码块中的比较从 nums[mid] > nums[mid + 1] 更改为至nums[mid] < nums[mid + 1] .