Joj*_*oji 3 javascript algorithm binary-search
这几天在刷LeetCode，遇到了挑战162.Find Peak Element：
\n\n\n峰值元素是严格大于其邻居的元素。
\n给定一个整数数组
\nnums，找到一个峰值元素，并返回其索引。如果数组包含多个 Peak，则返回任意 Peak 的索引。你可能会想象到
\nnums[-1] = nums[n] = -\xe2\x88\x9e。您必须编写一个及时运行的算法
\nO(log n)。限制条件：
\n\n
\n- \n
1 <= nums.length <= 1000- \n
-231 <= nums[i] <= 231 - 1- \n
nums[i] != nums[i + 1]对于所有有效的i
本题是关于使用二分查找来查找数组中的峰值元素。
\n我知道我们可以将数组视为交替的升序和降序序列。这是我的解决方案
\nvar findPeakElement = function(nums) {\n if(nums.length <= 1) return 0\n let left = 0, right = nums.length - 1\n \n while(left <= right) {\n const mid = left + right >>> 1\n if(nums[mid] > nums[mid + 1]) {\n right = mid - 1\n } else {\n left = mid + 1\n }\n }\n \n \n return left === nums.length ? left - 1 : left\n};\n如果nums[mid]大于数组中的下一个元素，我们知道我们处于降序子数组中，并且峰值元素必须位于左侧，反之亦然，如果nums[mid]小于下一个元素。到目前为止，一切都很好。但让我困惑的是我最终应该返回哪个索引 -left或者right？为了弄清楚这一点，我需要经历一系列的试验和错误。
如果我稍微调整问题以找到山谷元素，例如，[1, 3, 20, 4, 1, 0]山谷元素应该是0。虽然我可以推理如何缩小窗口，但我似乎仍然无法弄清楚在二分搜索结束时应该返回哪个索引。
这是我尝试通过镜像我所做的事情来返回数组中的山谷元素findPeakElement
var findValleyElement = function (nums) {\n if (nums.length <= 1) return 0\n let left = 0,\n right = nums.length - 1\n\n while (left <= right) {\n const mid = (left + right) >>> 1\n if (nums[mid] > nums[mid + 1]) {\n left = mid + 1\n } else {\n right = mid - 1\n }\n }\n\n return right\n}\n但这次我不能用作right返回的索引。我需要用left它来代替。如果不通过一堆示例，我似乎无法想到一种一致的思考方式，这确实不理想，因为您仍然可能会错过一些边缘情况。
所以我的问题是，在思考这些二分搜索问题时，我们是否可以采用一些一致的思维模型，特别是我们应该返回哪个索引来满足要求。
\n当以下条件成立时：
\nif(nums[mid] > nums[mid + 1]) {\n...那么这可能是mid一种解决方案，甚至可能是唯一的解决方案。因此，这意味着您不应将其从范围中排除，但right = mid - 1您确实将其排除。你应该设置right = mid. 为了避免潜在的无限循环，循环条件应该是left < right。这将确保循环始终结束：保证范围在每次迭代中变得更小*
* 让我们假设left == right + 1在某个时刻。然后mid将变得等于left（因为总和中的奇数位被 删除>>>）。现在要么我们做right = mid，要么我们做left = mid + 1。无论哪种情况我们都会得到left == right。在所有其他情况下left < right，我们得到的 amid严格位于这两个限制之间，然后范围肯定会变得更小。
一旦循环退出，left就等于right。该范围（1）中唯一可能的索引就是该索引。
现在不再需要检查是否left为nums.length，因为这不会发生：根据我们选择的while条件，left永远不会大于right，...只能等于它。由于right是一个有效的索引，因此不需要这种超出范围的检查。
另外数组大小为1的情况现在不需要特殊处理。
\n所以：
\nvar findPeakElement = function(nums) {\n let left = 0,\n right = nums.length - 1;\n\n while (left < right) {\n const mid = (left + right) >>> 1;\n if (nums[mid] > nums[mid + 1]) {\n right = mid;\n } else {\n left = mid + 1;\n }\n }\n\n return left;\n};\n\n\n这是我返回山谷元素的尝试
\n
如果你想找到谷元素，它并不总是有效，除非问题中的以下假设从此改变：
\n\n\n你可能会想象
\nnums[-1] = nums[n] = -\xe2\x88\x9e
...对此：
\n\n\n你可能会想象
\nnums[-1] = nums[n] = \xe2\x88\x9e
一旦达成一致，您只需将上述代码块中的比较从 更改nums[mid] > nums[mid + 1]为nums[mid] < nums[mid + 1]。
| 归档时间： |
|
| 查看次数： |
333 次 |
| 最近记录： |