Why does my binary search run slower than my linear search in MATLAB?

Question

Here is my code for binary search:

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;

And here is my linear search:

function linearFound = linearSearch(a, key)

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

In both cases, 'a' is an array of sorted integers and 'key' is the value I'm looking for. Having run multiple tests with a range of array sizes and averaging of runtimes, I consistently find my linear search to be faster than my binary search. I know from theory that the binary search is supposed to be faster. What am I doing wrong?

You can use the `profile` tool to check where is Matlab spending time, and see if it is a problem of algorithm or your implementation. I guess that, in your case, it has to do with memory handling and creating those 'half' arrays, but profiler can tell you better — Noel Segura Meraz, Mar 02 '17 at 04:19

smttsp · Answer 1 · 2017-03-02T16:45:22.473

Some of the problems:

1) You use recursion in binary search, so you have more function calls.

2) You create new matrix every time you call binarySearch

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

Matlab is clever enough not to create the same matrix over and over again but it has some cost.

3) You have some unnecessary piece of code like result=binaryFound. This is not even a nanosec but just saying

Here is a sample code I just wrote, I tested with few example but not thoroughly tested which is quite faster than your 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

EDIT: I forgot to tell the most important thing:

4) What is the key you are searching for?

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

So, if you are searching for the first element in the list, there is no way Binary Search can compete with Linear Search.

"Matlab is clever enough not to create the same matrix over and over again" -> I'm pretty sure the data is copied there, over and over again. A MATLAB matrix never points to partial data for another matrix. `b=a` doesn't copy data, but `b=a(5:10)` or even `a=a(5:10)` does copy data. — Cris Luengo, Jul 26 '19 at 15:59

Why does my binary search run slower than my linear search in MATLAB?

1 Answers1