我是否需要爲此實現一個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搜索？

回答

相關問題