バイナリ検索が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 

、「」ソートされた整数の配列され、「キー」であります私が探している価値。 配列サイズの範囲で複数のテストを実行し、ランタイムの平均化を行った結果、私のリニア検索はバイナリ検索よりも高速になることがわかりました。私はバイナリ検索がより速くなるはずであることを理論から知っています。私は間違って何をしていますか？

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 

EDITあるテストされていない、私はちょうど書いたサンプルコードも、ナノ秒ちょうどここ

を言っているではありません：最も重要なことを忘れた：

4）あなたが探しているキーは何ですか？

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

リストの最初の要素を探しているのであれば、バイナリ検索はリニア検索と競うことができる方法はありません。