Lua Program to Implement Ternary Search

Lua Program to Implement Ternary Search

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

Ternary Search is a fascinating algorithm designed for searching elements efficiently in a sorted array. Unlike Binary Search, which divides the array into two halves, Ternary Search splits it into three parts. By doing this, it can narrow down the search range more quickly in some cases, making it an interesting alternative to Binary Search. For beginners, Ternary Search is a great way to learn about recursive and divide-and-conquer techniques while practicing array handling in Lua.

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

Ternary Search is particularly useful in situations where you have a large, sorted dataset and need to perform frequent searches. It is widely applied in optimization problems, game development, and situations where minimizing comparisons matters. By understanding Ternary Search, beginners can strengthen their grasp of recursion, indexing, and efficient algorithm design while seeing firsthand how small changes in search strategy can affect performance.

Program 1: Iterative Ternary Search

This program demonstrates a simple iterative approach to Ternary Search. It searches for a target number in a sorted array by dividing it into three parts and checking the key positions.

-- Iterative Ternary Search in Lua

function ternarySearchIterative(arr, target)

    local left, right = 1, #arr

    while left <= right do

        local mid1 = left + math.floor((right - left) / 3)
        local mid2 = right - math.floor((right - left) / 3)

        if arr[mid1] == target then
            return mid1
        elseif arr[mid2] == target then
            return mid2
        elseif target < arr[mid1] then
            right = mid1 - 1
        elseif target > arr[mid2] then
            left = mid2 + 1
        else
            left = mid1 + 1
            right = mid2 - 1
        end

    end

    return -1

end

local numbers = {1, 3, 5, 7, 9, 11, 13}
local target = 7
local result = ternarySearchIterative(numbers, target)

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

This iterative approach calculates two mid-points to divide the array into three segments. By checking these points, the algorithm reduces the search space more efficiently than Linear Search. Beginners can appreciate how a small adjustment in dividing the array can improve search performance.

Program 2: Recursive Ternary Search

In this program, Ternary Search is implemented using recursion, which is a classic divide-and-conquer method. This approach is often cleaner and easier to read.

-- Recursive Ternary Search in Lua

function ternarySearchRecursive(arr, target, left, right)

    left = left or 1
    right = right or #arr

    if left > right then
        return -1
    end

    local mid1 = left + math.floor((right - left) / 3)
    local mid2 = right - math.floor((right - left) / 3)

    if arr[mid1] == target then
        return mid1
    elseif arr[mid2] == target then
        return mid2
    elseif target < arr[mid1] then
        return ternarySearchRecursive(arr, target, left, mid1 - 1)
    elseif target > arr[mid2] then
        return ternarySearchRecursive(arr, target, mid2 + 1, right)
    else
        return ternarySearchRecursive(arr, target, mid1 + 1, mid2 - 1)
    end

end

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

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

The recursive method repeatedly calls itself on smaller sections of the array, making it easier to understand for beginners learning divide-and-conquer strategies. It also demonstrates how recursion naturally handles multiple search regions without explicit loops.

Program 3: Ternary Search with Negative Numbers

Ternary Search can handle negative numbers just like positive ones, as comparisons remain valid. This example shows searching a sorted array containing negative values.

-- Ternary Search with negative numbers

function ternarySearchRecursive(arr, target, left, right)

    left = left or 1
    right = right or #arr

    if left > right then
        return -1
    end

    local mid1 = left + math.floor((right - left) / 3)
    local mid2 = right - math.floor((right - left) / 3)

    if arr[mid1] == target then
        return mid1
    elseif arr[mid2] == target then
        return mid2
    elseif target < arr[mid1] then
        return ternarySearchRecursive(arr, target, left, mid1 - 1)
    elseif target > arr[mid2] then
        return ternarySearchRecursive(arr, target, mid2 + 1, right)
    else
        return ternarySearchRecursive(arr, target, mid1 + 1, mid2 - 1)
    end

end

local numbers = {-30, -20, -10, 0, 10, 20, 30}
local target = -10

local result = ternarySearchRecursive(numbers, target)

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

By using the same recursive function, negative numbers are seamlessly supported. Beginners can see that the logic doesn’t need to change for arrays with negative values, making the algorithm versatile.

Program 4: Ternary Search with Floating-Point Numbers

Ternary Search also works with floating-point numbers. This is useful for applications like grades, measurements, or any decimal dataset.

-- Ternary Search with floating-point numbers

function ternarySearchRecursive(arr, target, left, right)

    left = left or 1
    right = right or #arr

    if left > right then
        return -1
    end

    local mid1 = left + math.floor((right - left) / 3)
    local mid2 = right - math.floor((right - left) / 3)

    if arr[mid1] == target then
        return mid1
    elseif arr[mid2] == target then
        return mid2
    elseif target < arr[mid1] then
        return ternarySearchRecursive(arr, target, left, mid1 - 1)
    elseif target > arr[mid2] then
        return ternarySearchRecursive(arr, target, mid2 + 1, right)
    else
        return ternarySearchRecursive(arr, target, mid1 + 1, mid2 - 1)
    end

end

local numbers = {0.1, 1.2, 2.3, 3.4, 4.5, 5.6}
local target = 3.4

local result = ternarySearchRecursive(numbers, target)

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

This shows the algorithm’s flexibility. Beginners can apply Ternary Search to any numeric type as long as the array remains sorted, demonstrating real-world applicability.

Program 5: Reusable Ternary Search Function

Here, the iterative Ternary Search is wrapped into a reusable function for easy integration into projects.

-- Reusable Ternary Search Function

function ternarySearch(arr, target)

    local left, right = 1, #arr

    while left <= right do

        local mid1 = left + math.floor((right - left) / 3)
        local mid2 = right - math.floor((right - left) / 3)

        if arr[mid1] == target then
            return mid1
        elseif arr[mid2] == target then
            return mid2
        elseif target < arr[mid1] then
            right = mid1 - 1
        elseif target > arr[mid2] then
            left = mid2 + 1
        else
            left = mid1 + 1
            right = mid2 - 1
        end

    end

    return -1

end

local numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9}
local target = 6
local index = ternarySearch(numbers, target)

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

This reusable function illustrates good programming practice. Beginners can see how wrapping logic into a function improves readability, reusability, and maintainability in larger projects.

Frequently Asked Questions (FAQ)

Ternary Search often raises questions for beginners:

Q1. Is Ternary Search better than Binary Search?
Ternary Search divides the array into three parts, but in most cases, Binary Search is slightly faster due to fewer comparisons per iteration. However, it is a good exercise in divide-and-conquer techniques.

Q2. Does Ternary Search only work on sorted arrays?
Yes, the array must be sorted for the algorithm to work correctly.

Q3. Can Ternary Search handle negative and floating-point numbers?
Absolutely. As long as comparisons are valid, Ternary Search works for any numeric type.

Q4. When should I use recursion vs. iteration?
Recursion is often cleaner and easier to read, but iteration can be more memory-efficient for large arrays.

Q5. How do I determine the mid-points?
Mid-points are calculated to divide the array into three nearly equal segments, usually using integer division.

Conclusion

Ternary Search is an interesting and efficient algorithm for searching in sorted arrays. By learning both iterative and recursive approaches in Lua, beginners gain valuable experience with divide-and-conquer methods and array manipulation. This article also showed how Ternary Search handles negative numbers and floating-point values, making it versatile for different datasets. By practicing these examples, you can improve your understanding of searching algorithms and write cleaner, more efficient code in Lua.

Recommended Courses

Related Posts

Scroll to Top