在未排序的数组中以对数时间搜索

Question

我目前正在学习《算法导论》的考试，并遇到了一个问题，我无法真正解决这个问题，问题是：你有一个包含n个整数的数组，前m个元素是偶数，其余元素都是奇数。你需要编写一个算法来查找m的值（查找最后一个偶数的索引），并且时间复杂度为O(log m)。

我想到了类似于二分查找的方法，如果是奇数就向左移动，如果是偶数就向右移动，直到找到最后一个偶数的索引，但这种方法的时间复杂度为O(log n)，而不是O(log m)。

- Bob

Answer 1

从索引1开始，不断将索引加倍，直到找到一个奇数条目。这给出了m的上限，时间复杂度为O(log m)。然后进行二分查找。

- Henrik

---

如果我错了，请纠正我。二分查找在最坏情况下需要O(log n)的时间复杂度。 - Chris

@Abody97 - 我显然是想在先前确定的上限为最多2m的范围内进行二分查找，因此二分查找也是O(log(m))。 - Henrik

哦，是的，对不起 :) 我忘记了 m 的上限最多为 2m 这个事实，非常抱歉 :) - Chris