我是否需要为此实现b-tree搜索？

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

你应该使用二进制搜索.Objective C甚至可以有一个内置的方法(我知道很多语言).除非您想将数据存储在磁盘上,否则B树可能不会有太大帮助.