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.

As I understand it, Binary search will always be faster if access times are constant (as in an array in RAM or cache), and Fibonacci search will be faster when the distance and access times, are proportional. Like on a hard drive or tape drive, where if the next item to be accessed is closer, the time to access it is much faster.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, learning, and sharing knowledge.