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

我有一个整数数组，它可能会遇到数十万（或更多），以数字升序排序，因为这是它们最初的堆叠方式。我是否需要为此实现一个b-tree搜索？

我需要能够查询该阵列得到一个号码>=一些输入的其第一出现的索引，尽可能有效地。我不知道如何去做这件事的唯一方法就是遍历数组，直到它返回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

把这个数据到数据库中，以便执行该搜索只会是一个不得已的解决方案，因为我希望看到某种算法在内存迅速解决这个。

我做有改变的数据结构，或以专卖店为我建立的阵列，因为我的计划已经由一个推每个号码一个到这个堆栈的附加数据结构的能力，所以我d只是修改将它们添加到堆栈的代码。在索引被添加到堆栈时搜索索引是不可能的，因为搜索操作将在事实之后经常以不同的值重复。

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

来源

2010-10-24 d11wtq

您应该使用binary search。 Objective C甚至可以有一个内置的方法（我知道很多语言）。除非要将数据存储在磁盘上，否则B树不会有太大的帮助。

来源

2010-10-24 13:44:14 svick

谢谢。现在阅读。 – d11wtq 2010-10-24 13:49:56

这很简单，正是我正在寻找的那种算法，谢谢。现在，我只是在踢我自己，这几个小时前我的脑袋里并没有流行！：P – d11wtq 2010-10-24 13:51:52

快速搜索算法应该能够处理这种规模的int数组没有考虑太久，我应该考虑（和数组进行排序，因此二进制搜索很可能是要走的路）。

我觉得B树可能是矫枉过正...

来源

2010-10-24 13:47:58 arcwhite

我不知道的Objective-C，而C（纯“醇C）中有一个名为bsearch（此外，据我所知的OBJ-C功能，可以调用C函数就好了）：

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

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

来源

2010-10-24 13:49:51

由于它们按特定的ASCending顺序排序，只需要更大的顺序，我会序列化该数组，并通过INT对其进行分解，并保留包含更大INT的序列化字符串部分，然后将其反序列化，瞧。

来源

2010-10-24 15:02:17 eliezer

线性搜索也被称为顺序搜索着眼于从开始序列中的每个元素，以查看是否所期望的元素存在于所述数据结构中。当数据量很小时，这个搜索是快速的。它很容易，但需要的工作量与要搜索的数据量成正比。如果期望的元素不存在，则元素数量将增加一倍来搜索。

二进制搜索是有效的较大的阵列。在这我们检查中间元素。如果价值更大，我们正在寻找，然后看看上半场，否则，看看下半场。重复此操作直至找到所需的项目。该表必须按二进制搜索进行排序。它在每次迭代中消除了一半的数据。其对数

来源

2014-09-17 10:33:11

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

回答

相关问题