爲什麼我的二進制搜索運行速度比我在MATLAB中的線性搜索慢？

這裏是我的二進制搜索代碼：爲什麼我的二進制搜索運行速度比我在MATLAB中的線性搜索慢？

function result = binarySearch(a, key) 

binaryFound = false; 
halfIndex = fix(length(a)/2) + 1; 

if a(halfIndex) == key 
    binaryFound = true; 
elseif length(a)==1 && a(1)~=key 
    binaryFound = false; 
elseif key > a(halfIndex) 
    newHalfArray = a(halfIndex+1:end); 
    binaryFound = binarySearch(newHalfArray, key); 
else 
    newHalfArray = a(1:halfIndex-1); 
    binaryFound = binarySearch(newHalfArray, key); 
end 
result = binaryFound;

，這裏是我的線性搜索：

function linearFound = linearSearch(a, key) 

linearFound = false; 
for j=1:length(a) 
    if a(j) == key 
     linearFound = true; 
    end 
end

在這兩種情況下，「A」是排序的整數數組和「鑰匙」是我正在尋找的價值。在運行多個測試時，使用一系列數組大小和運行時間平均值，我始終發現我的線性搜索比我的二進制搜索更快。我從理論上知道二進制搜索應該更快。我究竟做錯了什麼？

來源

2017-03-02 crimsonprotag

你可以使用'profile'工具來檢查Matlab花費的時間，看看它是算法還是你的實現問題。我想，就你而言，它與內存處理和創建這些'半'陣列有關，但profiler可以更好地告訴你 –

一些問題：

1）您在二進制搜索使用遞歸，讓你有更多的函數調用。

2）創建新的矩陣每次你打電話binarySearch

newHalfArray = a(1:halfIndex-1); //or 
newHalfArray = a(halfIndex+1:end);

Matlab是足夠聰明不要一遍又一遍地創建相同的矩陣再次但是它有一定的成本。

3）你有一些不必要的代碼，如result=binaryFound。這甚至不是一個納秒，但只是說

這裏是一個示例代碼，我只寫了，我有幾個例子測試，但沒有徹底測試這是相當快於你的二分查找

function found = binarySearch(a, key) 

found = false; 

beg = 1; 
fin = length(a); 
mid = floor(length(a)/2); 

while ~found 
    if a(mid) == key 
     found = true; 
    elseif fin-beg == 1 
     break 
    elseif a(mid) < key 
     beg = mid; 
     mid = ceil((fin+beg)/2); 
    elseif a(mid) > key 
     fin = mid; 
     mid = floor((fin+beg)/2); 
    end 
end 

end

編輯：我忘了告訴最重要的東西：

4）你在尋找什麼鑰匙？

 Best case  Avg case  Worst case 
LS  1 comparison n/2 comp.  n comp 
BS  1 comparison O(log_n)  O(log_n)

所以，如果你正在尋找列表中的第一個元素，沒有辦法二進制搜索可以與線性搜索競爭。

來源

2017-03-02 04:25:19 smttsp

爲什麼我的二進制搜索運行速度比我在MATLAB中的線性搜索慢？

回答

相關問題