algorithm - 我需要为此实现 b 树搜索吗？

Question

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

我需要尽可能高效地查询数组以获取它第一次出现的数字 >= 一些输入的索引。我什至不考虑它就知道如何做到这一点的唯一方法是遍历数组测试条件，直到它返回 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”，但老实说，我不知道如何实现一个，在我开始着手解决之前，我想知道是否有适合这个单一的算法用例更好？

Answer 1

你应该使用 binary search . Objective C 甚至可以为此提供一个内置方法(我知道的许多语言都有)。 B 树可能不会有太大帮助，除非您想将数据存储在磁盘上。