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.

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
         fsrch = discrd
      end if


Any tips on how to improve it would be great.

Thank you.

8 Years
Discussion Span
Last Post by Adak

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.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.