Exponential Search is an efficient algorithm designed to quickly find an element in a sorted array. It works by first identifying a range where the target element could exist and then performing a Binary Search within that range. This two-step approach allows the algorithm to be very fast for large datasets, especially when the element is located near the beginning of the array. For beginners, Exponential Search is a great way to combine simple iteration with Binary Search, demonstrating how algorithms can work together to improve efficiency.
This algorithm is widely used in computer science and real-world applications where searching through large, sorted datasets is required, such as in databases or gaming leaderboards. By understanding Exponential Search, beginners not only learn about array manipulation and indexing but also gain insights into optimizing search operations and applying classic algorithms effectively in Lua.
Program 1: Basic Exponential Search
This program demonstrates the basic Exponential Search algorithm using a loop to find the target range and Binary Search to locate the element precisely.
-- Basic Exponential Search in Lua
function binarySearch(arr, target, left, right)
left = left or 1
right = right or #arr
while left <= right do
local mid = math.floor((left + right) / 2)
if arr[mid] == target then
return mid
elseif arr[mid] < target then
left = mid + 1
else
right = mid - 1
end
end
return -1
end
function exponentialSearch(arr, target)
if arr[1] == target then
return 1
end
local i = 1
while i <= #arr and arr[i] <= target do
i = i * 2
end
return binarySearch(arr, target, math.floor(i/2), math.min(i, #arr))
end
local numbers = {1, 3, 5, 7, 9, 11, 13, 15, 17}
local target = 11
local result = exponentialSearch(numbers, target)
if result ~= -1 then
print("Number found at index: " .. result)
else
print("Number not found")
endThis basic version demonstrates how the exponential phase identifies a range where the target may exist, then Binary Search efficiently locates it. Beginners can see how combining two algorithms can improve search performance compared to a linear search.
Program 2: Recursive Exponential Search
This program implements Exponential Search using recursion for the Binary Search part, making the code cleaner and easier to read.
-- Recursive Exponential Search in Lua
function binarySearchRecursive(arr, target, left, right)
if left > right then
return -1
end
local mid = math.floor((left + right) / 2)
if arr[mid] == target then
return mid
elseif arr[mid] < target then
return binarySearchRecursive(arr, target, mid + 1, right)
else
return binarySearchRecursive(arr, target, left, mid - 1)
end
end
function exponentialSearchRecursive(arr, target)
if arr[1] == target then
return 1
end
local i = 1
while i <= #arr and arr[i] <= target do
i = i * 2
end
return binarySearchRecursive(arr, target, math.floor(i/2), math.min(i, #arr))
end
local numbers = {2, 4, 6, 8, 10, 12, 14, 16, 18}
local target = 12
local result = exponentialSearchRecursive(numbers, target)
if result ~= -1 then
print("Number found at index: " .. result)
else
print("Number not found")
endThe recursive version illustrates how recursion can replace loops in Binary Search while keeping the exponential range-finding phase iterative. Beginners can appreciate cleaner code and understand recursion in practice.
Program 3: Exponential Search with Negative Numbers
Exponential Search works with negative numbers just as easily as positive ones. This example shows searching a sorted array containing negative values.
-- Exponential Search with negative numbers
function binarySearch(arr, target, left, right)
left = left or 1
right = right or #arr
while left <= right do
local mid = math.floor((left + right) / 2)
if arr[mid] == target then
return mid
elseif arr[mid] < target then
left = mid + 1
else
right = mid - 1
end
end
return -1
end
function exponentialSearch(arr, target)
if arr[1] == target then
return 1
end
local i = 1
while i <= #arr and arr[i] <= target do
i = i * 2
end
return binarySearch(arr, target, math.floor(i/2), math.min(i, #arr))
end
local numbers = {-50, -30, -20, -10, 0, 10, 20, 30, 40}
local target = -10
local result = exponentialSearch(numbers, target)
if result ~= -1 then
print("Number found at index: " .. result)
else
print("Number not found")
endBy using the same search functions, negative numbers are supported without any changes. Beginners can see that the algorithm’s logic remains consistent regardless of the values in the array.
Program 4: Exponential Search with Floating-Point Numbers
This program shows that Exponential Search also works for floating-point numbers, such as decimals in measurements or scores.
-- Exponential Search with floating-point numbers
function binarySearch(arr, target, left, right)
left = left or 1
right = right or #arr
while left <= right do
local mid = math.floor((left + right) / 2)
if arr[mid] == target then
return mid
elseif arr[mid] < target then
left = mid + 1
else
right = mid - 1
end
end
return -1
end
function exponentialSearch(arr, target)
if arr[1] == target then
return 1
end
local i = 1
while i <= #arr and arr[i] <= target do
i = i * 2
end
return binarySearch(arr, target, math.floor(i/2), math.min(i, #arr))
end
local numbers = {0.5, 1.2, 2.8, 3.6, 4.4, 5.9}
local target = 3.6
local result = exponentialSearch(numbers, target)
if result ~= -1 then
print("Number found at index: " .. result)
else
print("Number not found")
endFloating-point support demonstrates the algorithm’s versatility. Beginners can confidently apply Exponential Search to any numeric dataset that is sorted.
Program 5: Reusable Exponential Search Function
Here we wrap Exponential Search into a reusable Lua function, making it easy to integrate into projects or larger programs.
-- Reusable Exponential Search Function
function binarySearch(arr, target, left, right)
left = left or 1
right = right or #arr
while left <= right do
local mid = math.floor((left + right) / 2)
if arr[mid] == target then
return mid
elseif arr[mid] < target then
left = mid + 1
else
right = mid - 1
end
end
return -1
end
function exponentialSearchReusable(arr, target)
if arr[1] == target then
return 1
end
local i = 1
while i <= #arr and arr[i] <= target do
i = i * 2
end
return binarySearch(arr, target, math.floor(i/2), math.min(i, #arr))
end
local numbers = {5, 10, 15, 20, 25, 30, 35}
local target = 25
local index = exponentialSearchReusable(numbers, target)
if index ~= -1 then
print("Target found at index: " .. index)
else
print("Target not found")
endThe reusable function shows good programming practice. Beginners can see how modular code improves readability and reusability across multiple projects or datasets.
Frequently Asked Questions (FAQ)
Exponential Search often raises beginner questions:
Q1. How is Exponential Search different from Binary Search?
Exponential Search first finds a range quickly using exponential steps, then performs Binary Search. It’s faster when the target is near the beginning of the array.
Q2. Does the array need to be sorted?
Yes, like all divide-and-conquer searches, the array must be sorted.
Q3. Can it handle negative or floating-point numbers?
Yes, as long as comparisons are valid, it works with any numeric type.
Q4. When should I use iterative vs. recursive Binary Search in Exponential Search?
Recursion is cleaner and easier to read, but iteration can save memory for large arrays.
Q5. Is Exponential Search faster than Linear Search?
Yes, especially on large, sorted arrays. Linear Search checks every element, while Exponential Search quickly narrows down the target range.
Conclusion
Exponential Search is a powerful algorithm that combines exponential range-finding with Binary Search to efficiently locate elements in sorted arrays. By exploring iterative, recursive, negative number, and floating-point implementations in Lua, beginners can understand how versatile and practical this method is. Practicing these examples strengthens your skills in array manipulation, recursion, and efficient searching, helping you write cleaner, faster code in Lua. With Exponential Search, finding elements becomes faster, smarter, and much more engaging.
