我有一個整數數組,它可能會遇到數十萬(或更多),以數字升序排序,因爲這是它們最初的堆疊方式。我是否需要爲此實現一個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」,但說實話,我不知道如何實現一個,在我離開之前就開始搞清楚了,我想知道是否有一個很好的算法適合這個單一用例更好?
謝謝。現在閱讀。 – d11wtq 2010-10-24 13:49:56
這很簡單,正是我正在尋找的那種算法,謝謝。現在,我只是在踢我自己,這幾個小時前我的腦袋裏並沒有流行! :P – d11wtq 2010-10-24 13:51:52