Ruby Program to Implement Fibonacci Search

Ruby Program to Implement Fibonacci Search

Leave a Comment • • Algorithm Example, Algorithm Implementation, Beginner Guide, Code Example, Data Structures, Fibonacci Search, Learn Ruby, Ruby, Ruby Programming, Searching Algorithm, Searching Algorithms, Tutorial

When it comes to searching efficiently in sorted data, Binary Search is usually the first choice, but there is another algorithm called Fibonacci Search that can also be very effective. Fibonacci Search uses Fibonacci numbers to divide the search space, reducing the number of comparisons needed to find the target element. This method is particularly useful when working with large arrays or datasets where each comparison is expensive.

Pluralsight Logo
Accelerate your tech career
with hands-on learning.
Whether you're a tech newbie or a total pro,
get the skills and confidence to land your next move.
Start 10-Day Free Trial

Fibonacci Search is based on the idea of narrowing down the search range using Fibonacci numbers instead of dividing by two like in Binary Search. It is widely applied in scenarios where the data structure is static and the array size is large, such as in database indexing or memory-efficient storage systems. For beginners, learning Fibonacci Search in Ruby helps to understand how mathematical sequences can be applied to optimize algorithm performance. In this article, we will explore multiple ways to implement Fibonacci Search with clear examples for practical learning.

Program 1: Iterative Fibonacci Search

This program demonstrates Fibonacci Search using an iterative approach to find a target value in a sorted array.

# Program 1: Iterative Fibonacci Search
def fibonacci_search(array, target)

  n = array.length
  fibMMm2 = 0
  fibMMm1 = 1
  fibM = fibMMm2 + fibMMm1

  while fibM < n

    fibMMm2 = fibMMm1
    fibMMm1 = fibM
    fibM = fibMMm2 + fibMMm1

  end

  offset = -1

  while fibM > 1

    i = [offset + fibMMm2, n - 1].min

    if array[i] < target

      fibM = fibMMm1
      fibMMm1 = fibMMm2
      fibMMm2 = fibM - fibMMm1
      offset = i

    elsif array[i] > target

      fibM = fibMMm2
      fibMMm1 = fibMMm1 - fibMMm2
      fibMMm2 = fibM - fibMMm1

    else
      return i
    end

  end

  if fibMMm1 == 1 && array[offset + 1] == target
    return offset + 1
  end

  -1

end

numbers = [1, 3, 5, 7, 9, 11, 13, 15, 17]
target = 11
index = fibonacci_search(numbers, target)

if index != -1
  puts "Element #{target} found at index #{index} (iterative)"
else
  puts "Element #{target} not found (iterative)"
end

This program uses Fibonacci numbers to calculate positions in the array for comparison. By doing so, the search interval is narrowed efficiently, which helps reduce the total number of comparisons. Beginners can see how sequences from mathematics can guide efficient searching.

Program 2: Recursive Fibonacci Search

Fibonacci Search can also be implemented recursively, which illustrates the divide-and-conquer principle.

# Program 2: Recursive Fibonacci Search
def fibonacci_recursive(array, target, fibM, fibMMm1, fibMMm2, offset)

  return -1 if fibM <= 1

  i = [offset + fibMMm2, array.length - 1].min

  if array[i] == target
    return i
  elsif array[i] < target
    fibonacci_recursive(array, target, fibMMm1, fibMMm2, fibMMm1 - fibMMm2, i)
  else
    fibonacci_recursive(array, target, fibMMm2, fibMMm1 - fibMMm2, fibMMm2 - (fibMMm1 - fibMMm2), offset)
  end

end

def fibonacci_search_recursive(array, target)

  n = array.length
  fibMMm2 = 0
  fibMMm1 = 1
  fibM = fibMMm2 + fibMMm1

  while fibM < n

    fibMMm2 = fibMMm1
    fibMMm1 = fibM
    fibM = fibMMm2 + fibMMm1

  end

  fibonacci_recursive(array, target, fibM, fibMMm1, fibMMm2, -1)

end

numbers = [2, 4, 6, 8, 10, 12, 14]
target = 8
index = fibonacci_search_recursive(numbers, target)

if index != -1
  puts "Element #{target} found at index #{index} (recursive)"
else
  puts "Element #{target} not found (recursive)"
end

The recursive approach helps beginners understand how the problem can be broken down into smaller subproblems, using Fibonacci numbers to determine the next search index.

Program 3: Fibonacci Search with Floating-Point Numbers

Fibonacci Search works for floating-point numbers as long as the array is sorted.

# Program 3: Fibonacci Search with floating-point numbers
def fibonacci_search(array, target)

  n = array.length
  fibMMm2 = 0
  fibMMm1 = 1
  fibM = fibMMm2 + fibMMm1

  while fibM < n

    fibMMm2 = fibMMm1
    fibMMm1 = fibM
    fibM = fibMMm2 + fibMMm1

  end

  offset = -1

  while fibM > 1

    i = [offset + fibMMm2, n - 1].min

    if array[i] < target

      fibM = fibMMm1
      fibMMm1 = fibMMm2
      fibMMm2 = fibM - fibMMm1
      offset = i

    elsif array[i] > target

      fibM = fibMMm2
      fibMMm1 = fibMMm1 - fibMMm2
      fibMMm2 = fibM - fibMMm1

    else
      return i
    end

  end

  if fibMMm1 == 1 && array[offset + 1] == target
    return offset + 1
  end

  -1

end

numbers = [0.5, 1.1, 2.4, 3.6, 4.8, 5.9]
target = 3.6

index = fibonacci_search(numbers, target)

if index != -1
  puts "Floating-point element #{target} found at index #{index}"
else
  puts "Floating-point element #{target} not found"
end

The algorithm relies on comparisons, so it naturally handles floats. Beginners can see that Fibonacci Search is versatile across numeric types.

Program 4: Fibonacci Search on Large Datasets

This program demonstrates how Fibonacci Search can efficiently locate elements in large sorted arrays.

# Program 4: Fibonacci Search on large dataset
def fibonacci_search(array, target)

  n = array.length
  fibMMm2 = 0
  fibMMm1 = 1
  fibM = fibMMm2 + fibMMm1

  while fibM < n

    fibMMm2 = fibMMm1
    fibMMm1 = fibM
    fibM = fibMMm2 + fibMMm1

  end

  offset = -1

  while fibM > 1

    i = [offset + fibMMm2, n - 1].min

    if array[i] < target

      fibM = fibMMm1
      fibMMm1 = fibMMm2
      fibMMm2 = fibM - fibMMm1
      offset = i

    elsif array[i] > target

      fibM = fibMMm2
      fibMMm1 = fibMMm1 - fibMMm2
      fibMMm2 = fibM - fibMMm1

    else
      return i
    end

  end

  if fibMMm1 == 1 && array[offset + 1] == target
    return offset + 1
  end

  -1

end

numbers = (1..1000).to_a
target = 678

index = fibonacci_search(numbers, target)

if index != -1
  puts "Element #{target} found at index #{index} in large dataset"
else
  puts "Element #{target} not found in large dataset"
end

By using Fibonacci numbers to calculate probe positions, the algorithm reduces unnecessary comparisons, making it suitable for large datasets. Beginners can understand how this approach improves efficiency compared to linear scanning.

Frequently Asked Questions (FAQ)

Fibonacci Search can raise some common questions for beginners:

Q1: What is the time complexity of Fibonacci Search?
The time complexity is O(log n), similar to Binary Search.

Q2: Can Fibonacci Search work on unsorted arrays?
No, the array must be sorted to ensure correct results.

Q3: When is Fibonacci Search preferred over Binary Search?
It can be slightly more efficient for certain systems where addition and subtraction are cheaper than division, or in sequential access memory systems.

Q4: Can Fibonacci Search handle floating-point numbers?
Yes, as long as the array is sorted.

Q5: Is Fibonacci Search commonly used in practice?
It is less common than Binary Search but can be useful in systems with sequential memory access or static arrays.

Conclusion

In this article, we explored how to implement Fibonacci Search in Ruby using iterative and recursive approaches, including handling floating-point numbers and large datasets. Fibonacci Search uses the mathematical properties of Fibonacci numbers to efficiently reduce the search space in sorted arrays. By practicing these examples, beginners can understand how mathematical sequences can optimize algorithm performance and improve search efficiency. Mastering Fibonacci Search gives programmers another powerful tool for handling large or sequentially accessed datasets effectively.

Recommended Courses

Related Posts

Scroll to Top