matlab - 为什么我的二分搜索比 MATLAB 中的线性搜索运行得慢？

Question

这是我的二分查找代码:

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”都是一个排序整数数组，“key”是我要查找的值。在使用一系列数组大小和平均运行时间运行多个测试后，我始终发现我的线性搜索比我的二分搜索更快。我从理论上知道二进制搜索应该更快。我做错了什么？

Answer 1

一些问题:

1) 你在二分查找中使用了递归，所以你有更多的函数调用。

2) 每次调用 binarySearch

时都会创建新矩阵

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

Matlab 足够聪明，不会一遍又一遍地创建相同的矩阵，但它有一些成本。

3) 你有一些不必要的代码，比如 result=binaryFound。 这甚至不是纳秒，只是说

这是我刚写的示例代码，我用几个例子进行了测试，但没有彻底测试，它比你的 BinarySearch 快得多

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) 您要搜索的 key 是什么？

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

因此，如果您要搜索列表中的第一个元素，则二分搜索无法与线性搜索竞争。