Member Avatar for beatlea

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.

  • 2 Contributors
  • 1 Reply
  • 139 Views
  • 3 Days Discussion Span
  • Latest Post Latest Post by Adak
Member Avatar for 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.

Be a part of the DaniWeb community

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