Lua Program to Implement Fibonacci Search

Lua Program to Implement Fibonacci Search

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

Fibonacci Search is an interesting and efficient algorithm for finding elements in a sorted array. Unlike Binary Search, which divides the array into halves, Fibonacci Search uses Fibonacci numbers to divide the array into smaller sections. This approach makes it particularly useful for searching in large arrays where the cost of accessing elements can vary, such as in databases or memory-sensitive applications. For beginners, learning Fibonacci Search is a great way to understand how mathematics, specifically the Fibonacci sequence, can be applied to solve practical programming problems.

Learn C Programming For Free on Windows

A beginner-friendly course that teaches real C programming using a Windows compiler. Learn arrays, pointers, functions, and file handling step by step with practical lessons.

Start Learning C Programming

The algorithm is based on the idea that any array can be split into sections proportional to Fibonacci numbers, allowing us to narrow down the search range step by step. This makes Fibonacci Search a unique and powerful alternative to Binary Search, especially when the array size is large. By implementing it in Lua, beginners can explore both algorithmic thinking and practical coding techniques, gaining a deeper understanding of array manipulation and search optimization.

Program 1: Basic Fibonacci Search

This program demonstrates the classic Fibonacci Search algorithm using a loop to find the target element in a sorted array.

-- Basic Fibonacci Search in Lua

function fibonacciSearch(arr, target)

    local n = #arr
    local fibMMm2 = 0
    local fibMMm1 = 1
    local fibM = fibMMm2 + fibMMm1

    while fibM < n do

        fibMMm2 = fibMMm1
        fibMMm1 = fibM
        fibM = fibMMm2 + fibMMm1

    end

    local offset = -1

    while fibM > 1 do

        local i = math.min(offset + fibMMm2 + 1, n)

        if arr[i] < target then

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

        elseif arr[i] > target then

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

        else
            return i
        end

    end

    if fibMMm1 == 1 and arr[offset + 2] == target then
        return offset + 2
    end

    return -1

end

local numbers = {1, 3, 5, 7, 9, 11, 13, 15}
local target = 11
local index = fibonacciSearch(numbers, target)

if index ~= -1 then
    print("Number found at index: " .. index)
else
    print("Number not found")
end

This basic example shows how Fibonacci Search iteratively narrows the search space using Fibonacci numbers. Beginners can see how mathematical sequences can guide algorithmic decisions effectively.

Program 2: Fibonacci Search with Recursive Helper

This program uses a recursive function to generate Fibonacci numbers and performs the search in a more modular style.

-- Recursive Fibonacci number generator
function fibonacci(n)

    if n <= 1 then
        return n
    else
        return fibonacci(n-1) + fibonacci(n-2)
    end

end

-- Fibonacci Search using recursion for Fibonacci sequence
function fibonacciSearchRecursive(arr, target)

    local n = #arr
    local fibMMm2 = 0
    local fibMMm1 = 1
    local fibM = fibMMm2 + fibMMm1

    while fibM < n do

        fibMMm2 = fibMMm1
        fibMMm1 = fibM
        fibM = fibMMm2 + fibMMm1

    end

    local offset = -1

    while fibM > 1 do

        local i = math.min(offset + fibMMm2 + 1, n)

        if arr[i] < target then

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

        elseif arr[i] > target then

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

        else
            return i
        end

    end

    if fibMMm1 == 1 and arr[offset + 2] == target then
        return offset + 2
    end

    return -1

end

local numbers = {2, 4, 6, 8, 10, 12, 14}
local target = 10
local index = fibonacciSearchRecursive(numbers, target)

if index ~= -1 then
    print("Number found at index: " .. index)
else
    print("Number not found")
end

This recursive helper shows how dividing responsibilities into smaller functions improves readability. Beginners learn modular programming while exploring the Fibonacci sequence.

Program 3: Fibonacci Search with Negative Numbers

This program searches a sorted array containing negative numbers.

-- Fibonacci Search supporting negative numbers

function fibonacciSearch(arr, target)

    local n = #arr
    local fibMMm2 = 0
    local fibMMm1 = 1
    local fibM = fibMMm2 + fibMMm1

    while fibM < n do

        fibMMm2 = fibMMm1
        fibMMm1 = fibM
        fibM = fibMMm2 + fibMMm1

    end

    local offset = -1

    while fibM > 1 do

        local i = math.min(offset + fibMMm2 + 1, n)

        if arr[i] < target then

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

        elseif arr[i] > target then

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

        else
            return i
        end

    end

    if fibMMm1 == 1 and arr[offset + 2] == target then
        return offset + 2
    end

    return -1

end

local numbers = {-20, -10, 0, 10, 20, 30, 40}
local target = -10
local index = fibonacciSearch(numbers, target)

if index ~= -1 then
    print("Number found at index: " .. index)
else
    print("Number not found")
end

The algorithm works seamlessly with negative values, showing that the logic of Fibonacci Search is not limited to positive integers.

Program 4: Fibonacci Search with Floating-Point Numbers

This example demonstrates searching an array of decimal numbers.

-- Fibonacci Search supporting floating-point numbers

function fibonacciSearch(arr, target)

    local n = #arr
    local fibMMm2 = 0
    local fibMMm1 = 1
    local fibM = fibMMm2 + fibMMm1

    while fibM < n do

        fibMMm2 = fibMMm1
        fibMMm1 = fibM
        fibM = fibMMm2 + fibMMm1

    end

    local offset = -1

    while fibM > 1 do

        local i = math.min(offset + fibMMm2 + 1, n)

        if arr[i] < target then

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

        elseif arr[i] > target then

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

        else
            return i
        end

    end

    if fibMMm1 == 1 and arr[offset + 2] == target then
        return offset + 2
    end

    return -1

end

local numbers = {0.5, 1.5, 2.5, 3.5, 4.5, 5.5}
local target = 3.5
local index = fibonacciSearch(numbers, target)

if index ~= -1 then
    print("Number found at index: " .. index)
else
    print("Number not found")
end

Floating-point support illustrates the flexibility of Fibonacci Search. Beginners see that as long as comparisons are valid, the algorithm can handle any numeric type.

Program 5: Reusable Fibonacci Search Function

Here we wrap Fibonacci Search into a reusable function for easier integration into projects.

-- Reusable Fibonacci Search function

function fibonacciSearchReusable(arr, target)

    local n = #arr
    local fibMMm2, fibMMm1, fibM = 0, 1, 1

    while fibM < n do
        fibMMm2, fibMMm1 = fibMMm1, fibM
        fibM = fibMMm2 + fibMMm1
    end

    local offset = -1

    while fibM > 1 do

        local i = math.min(offset + fibMMm2 + 1, n)
        if arr[i] < target then

            fibM, fibMMm1, fibMMm2 = fibMMm1, fibMMm2, fibM - fibMMm1
            offset = i - 1

        elseif arr[i] > target then

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

        else
            return i
        end

    end

    if fibMMm1 == 1 and arr[offset + 2] == target then
        return offset + 2
    end

    return -1

end

local numbers = {5, 10, 15, 20, 25, 30}
local target = 25
local index = fibonacciSearchReusable(numbers, target)

if index ~= -1 then
    print("Target found at index: " .. index)
else
    print("Target not found")
end

This reusable function demonstrates good coding practice. Beginners learn how to structure code for better readability, reusability, and practical application.

Frequently Asked Questions (FAQ)

Fibonacci Search raises common questions among beginners:

Q1. How is Fibonacci Search different from Binary Search?
Fibonacci Search uses Fibonacci numbers to split the array, whereas Binary Search always splits in half. This can be more efficient in some cases.

Q2. Does the array need to be sorted?
Yes, sorting is required; otherwise, the search will fail.

Q3. Can Fibonacci Search handle negative or floating-point numbers?
Yes, the algorithm works as long as comparisons are valid.

Q4. When should I use Fibonacci Search over Binary Search?
It can be preferable when memory access cost varies, or when the size of the array fits Fibonacci sequences better for optimization.

Q5. Is it fast for small arrays?
For small arrays, Binary or Linear Search may be simpler, but Fibonacci Search shines in larger datasets.

Conclusion

Fibonacci Search is a clever and efficient way to find elements in sorted arrays by leveraging the Fibonacci sequence. By exploring basic, recursive, negative number, floating-point, and reusable implementations in Lua, beginners gain a deeper understanding of algorithmic thinking and practical coding. Practicing these examples helps improve skills in array manipulation, efficient searching, and code organization. With Fibonacci Search, you can approach large datasets with confidence, precision, and efficiency.

Recommended Courses

Related Posts

Scroll to Top