代码之家 › 专栏 › 技术社区 › javaguy

在滚动的整数的排序数组中搜索

performance search algorithm

0

javaguy · 技术社区 · 14 年前

有没有一种简单的方法可以在这样的数组中进行搜索?以下是一些例子:

5 6 7 8 19 45 21 32 40  // Rolled over at 7 th element
15 22 32 45 121 341 40  // Rolled over at 7 th element
1 22 32 45 121 341 400  // Rolled over at 0 th element

4 回复 | 直到 14 年前

1

6

Nikita Rybak 14 年前

任何寻找“滚动”点的算法在最坏的情况下至少有O(n)复杂度。

想象一下,您对数组进行了排序,并检查了不到n个元素。例如,如果在数组中 1 2 3 4 5 6 7 8 9 10 你没有检查元素 4 ,我可以用 100 1 2 3 100 5 6 7 8 9 10

因此,您唯一的选择是遍历所有元素,直到找到rollover。

感谢 艾亚尔施耐德 一个有用的评论。

顺便说一句,我是这里唯一一个不懂“滚动”这个词的词源的人吗?

2

4

mtrw 14 年前

如果要进行多次搜索,可以使用线性搜索进行一次预处理,以获得所有滚动位置的索引,然后在每个部分中进行二进制搜索。

但如果你只想搜索一次,我想你必须做线性搜索。所以无论哪种方法都需要线性搜索。

如果您使用“先查找滚动更新”技术,并且您知道只有一个滚动更新点,那么您至少可以在找到该点后立即退出线性搜索。

3

2

Rohan Monga 14 年前

http://geeksforgeeks.org/?p=1068

4

0

Erkan Haspulat 14 年前

把数组看作一个数学函数,你想要的是函数的局部极大值。虽然我没有足够的知识来解释,你可能想做一些研究 Hill Climbing . 使用一些启发式方法,你也许能更有效地找到你的局部极大值。