查找数组中具有模式的最小元素
给定一个数组，其元素的值从第 0 个索引增加到某个 (k-1) 索引。在 k 处，该值最小，然后通过第 n 个元素再次开始增加。求最小元素。
本质上，它是将一个排序列表附加到另一个列表上；例如：(1, 2, 3, 4, 0, 1, 2, 3)。
我尝试过各种算法，例如构建最小堆、快速选择或简单遍历。但不能低于 O(n)。但是这个数组中有一个模式，表明二分搜索应该是可能的，并且复杂性应该类似于 O(log n)，但找不到任何东西。 想法？？
谢谢
An array is given such that its element's value increases from 0th index through some (k-1) index. At k the value is minimum, and than it starts increasing again through the nth element. Find the minimum element.
Essentially, its one sorted list appended to another; example: (1, 2, 3, 4, 0, 1, 2, 3).
I have tried all sorts of algorithm like buliding min-heap, quick select or just plain traversing. But cant get it below O(n). But there is a pattern in this array, something that suggest binary search kind of thing should be possible, and complexity should be something like O(log n), but cant find anything.
Thoughts ??
Thanks
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
否 掉落可以在任何地方，没有任何结构。
考虑极端情况，
它简化为寻找最小元素。
No The drop can be anywhere, there is no structure to this.
Consider the extremes
It reduces to finding the minimum element.
对递减范围进行广度二分搜索，在二分分割处有一个元素重叠。换句话说，如果您有 17 个元素，请比较元素
等，寻找左侧元素大于右侧元素的情况。
一旦找到这样的范围，就递归，在该范围内执行相同的二分搜索。
重复此操作，直到找到递减的相邻对。
平均复杂度不小于 O(log n)，最坏情况为 O(n)。任何人都可以得到更严格的平均复杂度估计吗？它看起来大约是 O(log n) 和 O(n) 之间的“中间”，但我不知道如何评估它。它还取决于对值范围和从一个成员到下一个成员的增量大小的任何附加约束。
如果元素之间的增量始终为 1，则存在 O(log n) 解决方案。
Do a breadth-wise binary search for a decreasing range, with a one-element overlap at the binary splits. In other words, if you had, say, 17 elements, compare elements
etc., looking for a case where the left element is greater than the right.
Once you find such a range, recurse, doing the same binary search within that range.
Repeat until you've found the decreasing adjacent pair.
The average complexity is not less than O(log n), with a worst-case of O(n). Can anyone get a tighter average-complexity estimate? It seems roughly "halfway between" O(log n) and O(n), but I don't see how to evaluate it. It also depends on any additional constraints on the ranges of values and size of increment from one member to the next.
If the increment between elements is always 1, there's an O(log n) solution.
它不能在小于 O(n) 的时间内完成。
这种最坏的情况将永远困扰着我们——
越来越多的例子
a1,a2,a3...ak,ak+1...an
仅具有一个偏差 ak < ak-1 例如 1,2,3,4,5,6,4,7,8,9,10
所有其他数字关于“k”或“ak”值的信息绝对为零
It can not be done in less then O(n).
The worst case of this kind will always keep troubling us -
An increasing list
a1,a2,a3....ak,ak+1... an
with just one deviation ak < ak-1 e.g. 1,2,3,4,5,6,4,7,8,9,10
And all other numbers hold absolutely zero information about value of 'k' or 'ak'
最简单的解决方案是向前查找列表，直到下一个值小于当前值，或者向后查找大于当前值的值。即 O(n)。
同时执行这两项操作仍然是 O(n)，但运行时间可能会更快（取决于复杂的处理器/缓存因素）。
我不认为你能在算法上比 O(n) 更快地得到它，因为许多分而治之的搜索算法依赖于排序的数据集。
The simplest solution is to just look forward through the list until the next value is less than the current one, or backward to find a value that is greater than the current one. That is O(n).
Doing both concurrently would still be O(n) but the running time would probably be faster (depending on complicated processor/cache factors).
I don't think you can get it much faster algorithmically than O(n) since a lot of the divide-and-conquer search algorithms rely on having a sorted data set.