给定一个有n个元素的数组。数组中前m个元素已按升序排序(无重复项)且不为零。数组的其余部分为零。
应注意m未知 - 它可能是任何值,但已知n远大于m。
现在,如果x存在于数组中,则应返回其索引,否则它不存在。现在问题是,我必须找到一种能够实现此目的的算法。
扫描数组直到下一个元素不是零,时间复杂度为O(m);或者使用“二分查找”的修改版本,时间复杂度为O(logn),这两种方法都是微不足道的答案。除此之外我没有头绪。我们可以通过在O(log m)的时间内找到m来在前m个元素上进行二分查找,然后在O(logm)的时间内找到x,这一点已经被提出了提示。
应注意m未知 - 它可能是任何值,但已知n远大于m。
现在,如果x存在于数组中,则应返回其索引,否则它不存在。现在问题是,我必须找到一种能够实现此目的的算法。
扫描数组直到下一个元素不是零,时间复杂度为O(m);或者使用“二分查找”的修改版本,时间复杂度为O(logn),这两种方法都是微不足道的答案。除此之外我没有头绪。我们可以通过在O(log m)的时间内找到m来在前m个元素上进行二分查找,然后在O(logm)的时间内找到x,这一点已经被提出了提示。
m
个元素中进行二分查找是正确的方法。 - m.raynal