2

我有一个整数数组，可以达到数十万（或更多），按数字升序排序，因为它们最初是这样堆叠的。

我需要能够>=尽可能高效地查询数组以获取其第一次出现的数字某个输入的索引。我什至不考虑它就知道如何做到这一点的唯一方法是遍历数组测试条件，直到它返回 true，此时我将停止迭代。然而，这是解决这个问题的最昂贵的解决方案，我正在寻找解决它的最佳算法。

我正在使用 Objective-C 进行编码，但我将给出一个 JavaScript 示例，以扩大能够做出响应的人的受众。

// Sample set
var numbers = [1, 7, 23, 23, 23, 89, 1002, 1003];

var indexAfter100 = getIndexOfValueGreaterThan(100);
var indexAfter7 = getIndexOfValueGreaterThan(7);

// (indexAfter100 == 6) == true
// (indexAfter7 == 2) == true

将这些数据放入数据库以执行此搜索只会是最后的解决方案，因为我很想看到某种算法在内存中快速解决这个问题。

我确实有能力改变数据结构，或者在我构建数组时存储一个额外的数据结构，因为我的程序已经将每个数字一个一个地推到这个堆栈上，所以我只需修改代码将它们添加到堆栈中。在将索引添加到堆栈时搜索索引是不可能的，因为搜索操作会在事后以不同的值频繁重复。

现在我在想“B-Tree”，但老实说，我不知道如何实现一个，在我开始弄清楚之前，我想知道是否有适合这个单一用例的好算法更好的？

4

5 回答 5

7

你应该使用二分搜索。Objective C 甚至可以有一个内置的方法（我知道的许多语言都有）。除非您想将数据存储在磁盘上，否则 B-tree 可能不会有太大帮助。

于 2010-10-24T13:44:14.147 回答
2

我不了解Objective-C，但是C（plain 'ol C）带有一个名为的函数bsearch（此外，AFAIK，Obj-C可以很好地调用C函数）：

http://www.cplusplus.com/reference/clibrary/cstdlib/bsearch/

这基本上是进行二进制搜索，这听起来像是你需要的。

于 2010-10-24T13:49:51.753 回答
1

我应该认为，快速搜索算法应该能够处理该大小的整数数组而不会花费太长时间（并且数组已排序，因此二进制搜索可能是要走的路）。

我认为btree可能是矫枉过正......

于 2010-10-24T13:47:58.150 回答
0

由于它们以特定的 ASCending 顺序排序并且您只需要较大的数组，因此我将序列化该数组，将其分解为 INT 并保留序列化字符串中包含较大 INT 的部分，然后对其进行反序列化并瞧。

于 2010-10-24T15:02:17.467 回答
0

线性搜索也称为顺序搜索，从一开始就按顺序查看每个元素，以查看所需元素是否存在于数据结构中。当数据量较小时，这种搜索速度很快。它很容易，但所需的工作与要搜索的数据量成正比。如果所需元素不存在，则元素数量加倍将使搜索时间加倍。

对于较大的数组，二分查找是有效的。在此我们检查中间元素。如果值大于我们要查找的值，则查看前半部分；否则，查看后半部分。重复此操作，直到找到所需的项目。必须对表进行排序以进行二分查找。它在每次迭代中消除了一半的数据。它的对数

于 2014-09-17T10:33:11.050 回答