Binary Search is one of the most efficient and widely used search algorithms in programming. Unlike Linear Search, which checks each element one by one, Binary Search works by dividing a sorted array into halves and eliminating half of the remaining elements with each comparison. This “divide and conquer” strategy makes it much faster, especially for large datasets, and helps beginners understand how algorithms can optimize performance.
Binary Search is essential for tasks where you need quick lookups in sorted data, such as searching in databases, looking up words in a dictionary, or handling ordered numbers in games or applications. Learning Binary Search in Lua not only teaches array manipulation but also introduces recursion and loop logic in a practical context. By the end of this article, you will understand multiple ways to implement Binary Search and see it in action with numbers, negative values, and floating-point numbers.
Program 1: Iterative Binary Search
This first program demonstrates Binary Search using a simple loop. It searches for a target number in a sorted array.
-- Iterative Binary Search in Lua
function binarySearch(arr, target)
local low = 1
local high = #arr
while low <= high do
local mid = math.floor((low + high) / 2)
if arr[mid] == target then
return mid
elseif arr[mid] < target then
low = mid + 1
else
high = mid - 1
end
end
return -1
end
local numbers = {1, 3, 5, 7, 9, 11}
local target = 7
local result = binarySearch(numbers, target)
if result ~= -1 then
print("Number found at position: " .. result)
else
print("Number not found")
endIn this program, the low and high pointers keep track of the current search range. The middle element is checked against the target. If it matches, the index is returned; if not, half of the array is discarded, and the search continues. Beginners can see how loops can efficiently narrow down the search range.
Program 2: Recursive Binary Search
This version demonstrates a recursive approach, where the function calls itself with a smaller range until the target is found or the range is empty.
-- Recursive Binary Search in Lua
function recursiveBinarySearch(arr, target, low, high)
low = low or 1
high = high or #arr
if low > high then
return -1
end
local mid = math.floor((low + high) / 2)
if arr[mid] == target then
return mid
elseif arr[mid] < target then
return recursiveBinarySearch(arr, target, mid + 1, high)
else
return recursiveBinarySearch(arr, target, low, mid - 1)
end
end
local numbers = {2, 4, 6, 8, 10, 12}
local target = 10
local result = recursiveBinarySearch(numbers, target)
if result ~= -1 then
print("Number found at index: " .. result)
else
print("Number not found")
endRecursion in Binary Search simplifies the logic by letting the function call itself for the next half. Beginners can understand how recursion helps break problems into smaller, manageable tasks and see the power of divide and conquer.
Program 3: Binary Search with negative numbers
Binary Search works perfectly with negative numbers because comparisons do not depend on positivity. This program shows a search in a sorted array containing negative values.
-- Binary Search with negative numbers
function binarySearch(arr, target)
local low = 1
local high = #arr
while low <= high do
local mid = math.floor((low + high) / 2)
if arr[mid] == target then
return mid
elseif arr[mid] < target then
low = mid + 1
else
high = mid - 1
end
end
return -1
end
local numbers = {-10, -5, 0, 5, 10, 15}
local target = -5
local result = binarySearch(numbers, target)
if result ~= -1 then
print("Number found at index: " .. result)
else
print("Number not found")
endBeginners can see that Binary Search handles both negative and positive numbers seamlessly, emphasizing its flexibility in numeric datasets.
Program 4: Binary Search with floating-point numbers
Binary Search also works with decimal numbers. This example searches for a target in an array of floating-point values.
-- Binary Search with floating-point numbers
function binarySearch(arr, target)
local low = 1
local high = #arr
while low <= high do
local mid = math.floor((low + high) / 2)
if arr[mid] == target then
return mid
elseif arr[mid] < target then
low = mid + 1
else
high = mid - 1
end
end
return -1
end
local numbers = {1.1, 2.5, 3.3, 4.8, 5.9}
local target = 4.8
local result = binarySearch(numbers, target)
if result ~= -1 then
print("Number found at position: " .. result)
else
print("Number not found")
endThis program demonstrates that Binary Search relies on comparisons rather than indices or integers, making it suitable for floating-point numbers without any modifications.
Program 5: Generic reusable Binary Search function
This version wraps Binary Search in a reusable function suitable for any sorted numeric array. It combines iterative searching with easy integration into larger projects.
-- Reusable Binary Search function
function binarySearch(arr, target)
local low = 1
local high = #arr
while low <= high do
local mid = math.floor((low + high) / 2)
if arr[mid] == target then
return mid
elseif arr[mid] < target then
low = mid + 1
else
high = mid - 1
end
end
return -1
end
local numbers = {-3, 0, 2, 4, 7, 11, 15}
local target = 7
local index = binarySearch(numbers, target)
if index ~= -1 then
print("Target found at index: " .. index)
else
print("Target not found")
endBeginners can learn how to package the search logic into a reusable function, making it easier to use across different projects while maintaining clarity and efficiency.
Frequently Asked Questions (FAQ)
Binary Search can raise questions for beginners. Here are some common queries:
Q1. Does Binary Search require a sorted array?
Yes, Binary Search only works correctly on arrays sorted in ascending or descending order.
Q2. Is Binary Search faster than Linear Search?
Yes, Binary Search is much faster on large datasets, reducing comparisons from O(n) to O(log n).
Q3. Can Binary Search work with negative numbers?
Absolutely. Binary Search works with negative numbers and floating-point numbers because it only relies on comparisons.
Q4. Should I use recursion or iteration for Binary Search?
Both work well. Iteration is generally more memory-efficient, while recursion can make the code cleaner and easier to understand.
Q5. What happens if the target is not in the array?
Binary Search returns -1 or a similar indicator to show that the target was not found.
Conclusion
Binary Search is a fundamental algorithm that teaches beginners about efficient searching, recursion, and loops. In this article, you explored multiple ways to implement it in Lua, including iterative and recursive methods, and saw how it works with negative and floating-point numbers. Practicing these examples helps strengthen your understanding of algorithmic thinking and prepares you for more advanced search and sorting techniques. By mastering Binary Search, you gain a powerful tool for quickly finding values in sorted datasets.
