JS 中的二进制搜索：试图找到一致的心智模型

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] 小于下一个元素。到目前为止，一切都很好。但是让我困惑的是我最终应该 return 哪个索引 - left 或 right？为了弄清楚这一点，我需要经过大量的试验和错误。

如果我稍微修改问题以找到 谷元素 例如[1, 3, 20, 4, 1, 0] 的谷元素应该是 0。虽然我可以推断我们如何缩小 window 但我似乎仍然无法弄清楚在二进制搜索结束时我应该 return 哪个索引。

这是我尝试 return 通过镜像我对 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 作为returned 索引。我需要改用 left 。如果不通过一堆示例，我似乎无法想出一种一致的思考方式，这确实不理想，因为您仍然可能会错过一些边缘情况。

所以我的问题是，在思考这些二分查找问题时，我们是否可以采用一些一致的心智模型，具体来说，我们应该return满足要求的索引。

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 index.

现在不再需要检查 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]。

Answer 2

A peak 定义为其邻居均小于该元素的任何元素。在下面的示例中，有两个峰值元素，5 和 4 -

        5,
          4,        4,
      3,          3,  3,
    2,      2,  2,      2 ]
[ 1,          1,

所以我们可以从输入中取出三个元素，a、b、c 和 -

如果任何 a、b 或 c 为空，则无法进行有效比较，因此没有峰值。停止程序
否则如果 a < b 和 b > c，则已找到峰。输出峰值
最终下降 a，并在同一输入上重复搜索其他峰值

看起来像这样 -

function* peaks ([ a, b, c, ...more ]) {
  if (a == null || b == null || c == null) return // 1
  if (a < b && b > c) yield b                     // 2
  yield *peaks([ b, c, ...more ])                 // 3
}

for (const p of peaks([1,2,1,3,4,5,4,2,1,5,6,7,4]))
  console.log("found peak", p)

found peak 2
found peak 5
found peak 7

如果你有一个非常大的输入，我相信 LeetCode 会给你，像这样处理数组会产生大量浪费的中间值。更好的方法是使用索引，i -

function* peaks (t, i = 0) {
  let a = t[i], b = t[i + 1], c = t[i + 2]
  if (a == null || b == null || c == null) return // 1
  if (a < b && b > c) yield b                     // 2
  yield *peaks(t, i + 1)                          // 3
}

for (const p of peaks([1,2,1,3,4,5,4,2,1,5,6,7,4]))
  console.log("found peak", p)

found peak 2
found peak 5
found peak 7

最后，递归的使用将限制该程序可以处理的输入大小。我们可以使用 for 循环来避免任何递归限制 -

function* peaks (t) {
  let a, b, c
  for (let i = 0; i<t.length; i++) {
    a = t[i], b = t[i + 1], c = t[i + 2]
    if (a == null || b == null || c == null) return // 1
    if (a < b && b > c) yield b                     // 2
  }
}

for (const p of peaks([1,2,1,3,4,5,4,2,1,5,6,7,4]))
  console.log("found peak", p)

found peak 2
found peak 5
found peak 7

在最后两个示例中，我们每步执行三个数组查找，t[i]、t[i + 1] 和 t[i + 2]。作为一种优化，我们可以将其减少到仅一次查找 -

function* peaks (t) {
  let a, b, c
  for (let i = 0; i<t.length; i++) {
    a = b, b = c, c = t[i]
    if (a == null || b == null || c == null) continue
    if (a < b && b > c) yield b
  }
}

for (const p of peaks([1,2,1,3,4,5,4,2,1,5,6,7,4]))
  console.log("found peak", p)

found peak 2
found peak 5
found peak 7

这是有效的，因为我们的程序有效地将 a、b 和 c 中的元素“向左”移动。注意 b 列中的峰值 -

a	b	c	...
null	null	1	2,1,3,4,5,4,2,1,5,6,7,4
null	1	2	1,3,4,5,4,2,1,5,6,7,4
1	2 (peak)	1	3,4,5,4,2,1,5,6,7,4
2	1	3	4,5,4,2,1,5,6,7,4
1	3	4	5,4,2,1,5,6,7,4
3	4	5	4,2,1,5,6,7,4
4	5 (peak)	4	2,1,5,6,7,4
5	4	2	1,5,6,7,4
4	2	1	5,6,7,4
2	1	5	6,7,4
1	5	6	7,4
5	6	7	4
6	7 (peak)	4

通过我们优化的程序，我们可以放弃其他几个不必要的操作。不再需要索引 i，我们可以不必担心由 i++ 和 i<t.length 的比较引起的逐一错误。此外，我们可以跳过 c == null 检查，因为 c 将始终代表输入数组的一个元素 -

function* peaks (t) {
  let a, b, c
  for (const v of t) {
    a = b, b = c, c = v
    if (a == null || b == null) continue
    if (a < b && b > c) yield b
  }
}

for (const p of peaks([1,2,1,3,4,5,4,2,1,5,6,7,4]))
  console.log("found peak", p)

found peak 2
found peak 5
found peak 7

如果你想收集所有的峰，你可以使用Array.from将任何可迭代转换为数组-

const allPeaks = peaks([1,2,1,3,4,5,4,2,1,5,6,7,4])
console.log(allPeaks)

[2, 5, 7]

生成器非常适合这类问题，因为它们可以在任何时候 paused/canceled，即在找到第一个峰值之后 -

const firstPeak (t) {
  for (const p of peaks(t))
    return p                 // <- immediately stops `peaks`
}

firstPeak([1,2,1,3,4,5,4,2,1,5,6,7,4])

但是，如果您想在不使用生成器的情况下编写 firstPeaks，没有什么可以阻止您这样做。您可以简单地 return -

而不是使用 yield

function firstPeak (t) {
  let a, b, c
  for (const v of t) {
    a = b, b = c, c = v
    if (a == null || b == null) continue
    if (a < b && b > c) return b          // <-
  }
}

console.log("first peak", firstPeak([1,2,1,3,4,5,4,2,1,5,6,7,4]))

first peak 2

Answer 3

由于数组的上限为 1000 个元素，因此简单扫描是常数时间。如果我们想象 n（数组的大小）和 k（限制在 -k 到 +k 范围内的值）可以增长，那么使用 trincot 的答案，将 right 的初始选择修改为上限为 min(2k , n) 因为最大的连续增长是 2k+1.

def f(arr)
  0.upto(998) do |i|
    return arr[i] if arr[i+1] < arr[i]
  end
  return arr[999] # if we reach this, arr[998] < arr[999] and arr[1000] is -infinity
end

JS 中的二进制搜索：试图找到一致的心智模型

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

javascript

algorithm

binary-search

Constraints:

谷而不是峰