algorithm - 如何在由升序数组和降序数组组成的数组中找到最大数

Question

对于像这样的数组[1, 2, 4, 6, 8, 7, 5]，我们如何有效地找到其中的最大数？我们知道数组的第一部分1, 2, 4, 6,是升序排序的，第二部分是8, 7, 5降序排​​序的数组。

简单的解决方案是遍历数组，但鉴于数组由两个排序数组组成，我会想象搜索可以通过某种二进制搜索变体来完成，以实现o(logn)运行时复杂性。但是我似乎无法提出解决方案。

标签： algorithmbinary-search

Answer 1

你所要求的相当于找到一个数组的“峰值”。这是问题的对数时间解决方案