查找预排序数组中的两个元素总和等于某个值

我正在处理作业问题，并且在创建O（n * logn）解决方案时遇到了一些困难。我需要编写一个函数，它需要一个预先分类的数组和一个值来搜索。然后我需要查找数组中任何两个元素的和是否等于该值。查找预排序数组中的两个元素总和等于某个值

我需要创建两个O（n）和O（N * LOGN）这个算法。 O（n）很容易创建;但是，如果不添加一些实际上无助于解决问题的免费代码，则无法创建O（n * logn）算法。如果有人可以给我一些关于我可能会错过的指针，将不胜感激。

2010-02-05 JohnT

你是怎么做到的O（n）？ – letsc 2011-07-09 17:54:19

@letsc：使用两个索引a和b;用a = 1和b = n初始化。检查索引a和b中的元素总和。如果总和是你的目标，停下来，你找到了元素。如果总和较低，则增加一个;如果它较低，则减少b。当a = b时，停止，没有元素匹配。因为元素是排序的，所以你只会跳过你认为不是候选人的对。 – Joubarc 2012-07-04 14:30:08

从第一个元素开始，然后依次执行。尽管如此，使用二分搜索搜索第二个元素。

来源

2010-02-05 01:31:01 AraK

谢谢。我不能相信我错过了这一点。 – JohnT 2010-02-05 01:35:07

因为他们是预先排序，你可以使用二进制搜索和线性搜索

来源

2010-02-05 01:31:22

查找预排序数组中的两个元素总和等于某个值

回答

相关问题