arrays - 在先减后增的数组中搜索

Question

我有一个最初按降序排列的数组。 现在我遍历到数组中的一个随机索引，然后我翻转列表，使列表的其余部分变为升序。

现在给定一个数字，需要找到它的索引。 找到给定数字的索引的有效算法是什么？

例如:

初始列表:50 48 21 15 9 8 7 5 3 2 1

在数字 9 处翻转后: 50 48 21 15 1 2 3 5 7 8 9

提供的数量: 21

21 的索引:？

编辑 1: 有趣的是，按降序排列的列表的最小值元素将始终大于按升序排列的列表的最大值元素，因为它最初是列表的一部分按降序排列。

Answer 1

这是this question and answer的倒数, 序列上升然后再次下降。在你的情况下，它先下降然后再上升。

关键是从找到最小元素的索引开始。一旦有了它，就可以在左侧(递减)部分进行二分查找，在右侧(递增)部分进行二分查找。由于二进制搜索可以在对数时间内完成，因此只要您能在对数时间内找到最小元素，就可以在对数时间内完成所有操作。

幸运的是，您还可以使用二分查找来做到这一点。对于您考虑的数组中的任何位置，如果以下元素更大，则您位于右侧(增加)部分；如果它更小，那么你就在左边(递减)部分。这足以让您执行二分搜索以找到最小值。