0

Hello,

I coded binary and Fibonacci search algorithms in Fortran and was trying to determine for what size of array Fibonacci search would become faster than the binary search. Unfortunately, what I get is the binary search being quicker on any given array.

Here is my implementation of the Fibonacci search.

```
integer function fsrch(array,size,item)
real array(size), item
integer size
integer fib(48), bsrch2, k, discrd, index
intent (in) :: size, array, item
discrd = 0
c Precomputed Fibonacci numbers F0 up to F47.
data fib(1)/ 0/, fib(2)/ 1/, fib(3)/ 1/, fib(4)/ 2/, fib(5)/ 3/
+fib(6)/ 5/, fib(7)/ 8/, fib(8)/ 13/, fib(9)/ 21/,fib(10)/ 34/
+fib(11)/ 55/, fib(12)/ 89/, fib(13)/ 144/, fib(14)/ 233/
+fib(15)/ 377/, fib(16)/ 610/, fib(17)/ 987/, fib(18)/ 1597/
+fib(19)/ 2584/, fib(20)/ 4181/, fib(21)/ 6765/
+fib(22)/ 10946/, fib(23)/ 17711/, fib(24)/ 28657/
+fib(25)/ 46368/, fib(26)/ 75025/, fib(27)/ 121393/
+fib(28)/ 196418/, fib(29)/ 317811/, fib(30)/ 514229/
+fib(31)/ 832040/, fib(32)/ 1346269/, fib(33)/ 2178309/
+fib(34)/ 3524578/, fib(35)/ 5702887/, fib(36)/ 9227465/
+fib(37)/ 14930352/, fib(38)/ 24157817/, fib(39)/ 39088169/
+fib(40)/ 63245986/, fib(41)/ 102334155/, fib(42)/ 165580141/
+fib(43)/ 267914296/, fib(44)/ 433494437/, fib(45)/ 701408733/
+fib(46)/ 1134903170/, fib(47)/ 1836311903/
+fib(48)/ 2147483647/
c Find the smallest Fibonacci number that is greater or equal to array size.
k=bsrch2(fib,48,size)
c If k = 0, stop. There is no match; the item is not in the array
10 if (k .ne. 0) then
index = fib(k-1) + discrd
c If element Fk-1 is beyond the end of the array, we pretend that the array
c is padded with elements larger than the sought item.
if (index .gt. size) then
k = k-1
goto 10
c Compare the item against element in Fk-1
c If the item is less than entry Fk-1, discard the elements from positions
c Fk-1 to n. Set k = k - 1 and return to 10.
else if (item .lt. array(index)) then
k = k-1
goto 10
c If the item is greater than entry Fk-1, discard the elements from positions
c 1 to Fk-1. Set k = k - 2, and return to 10.
else if (item .gt. array(index)) then
discrd = index
k = k-2
goto 10
end if
c If the item matches, stop.
end if
c Return the result or the index of the nearest lower item if the item was not found.
if (item .eq. array(index)) then
fsrch = index
else
fsrch = discrd
end if
return
end
```

Any tips on how to improve it would be great.

Thank you.