我有一个整数数组,它可以运行到数十万(或更多),按数字升序排序,因为这是它们最初的堆叠方式。
我需要能够查询数组,以尽可能高效地获取其第一次出现的数字>=
的索引。我知道的唯一方法是在不考虑它的情况下迭代数组测试条件,直到它返回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”,但老实说,我不知道如何实现它,在我开始研究它之前,我想知道是否有一个很好的算法更适合这个单一的用例?
最佳答案
你应该使用binary search。目标C甚至可以有一个内置的方法(我知道很多语言都有)除非你想把数据存储在磁盘上,否则b-tree可能不会有多大帮助。