为什么我的二进制搜索运行速度比我在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中的线性搜索慢？

回答

相关问题