Binary search algorithm
An example of the implementation of a binary search algorithm in the Julia programming language, designed to search for a given element in a sorted array.
Introduction
Binary search is an efficient algorithm for searching for an element in a sorted array. The basic idea is to divide the array in half at each step and compare the desired element with the element in the middle. This allows you to significantly reduce the number of operations compared to linear search. The algorithm has a time complexity which makes it very fast for large amounts of data.
The algorithm solves the problem of searching for a specific value in an ordered data set. It is widely used in computer science, databases, sorting algorithms, and other fields where a quick element search is required.
The main part
Definition of function and parameters
Function binarysearch accepts a sorted vector lst and the desired value val. The function is parameterized by the type T, which allows you to work with any type of data
function binarysearch(lst::Vector{T}, val::T) where T
# Initializing the lower limit of the search
low = 1
# Initializing the upper bound of the search (array length)
high = length(lst)
# # Main search cycle
# We continue to search until the lower limit exceeds the upper limit.
while low ≤ high
# We find the middle of the current range
# The ÷ operator performs integer division
mid = (low + high) ÷ 2
# Comparing the element in the middle with the desired value
if lst[mid] > val
# If the element in the middle is larger than the one you are looking for,
# shifting the upper border to the position in front of the middle
high = mid - 1
elseif lst[mid] < val
# If the element in the middle is smaller than the one you are looking for,
# we move the lower border to the position after the middle
low = mid + 1
else
# If the element in the middle is equal to the one you are looking for,
# returning the index of the found element
return mid
end
end
# # Handling the case when the element is not found
# If we are out of the loop, then the element is not found.
# We return 0 as a sign of missing element.
# (in Julia, indexing starts at 1, so 0 is not a valid index)
return 0
end
An example of using the function
Creating a sorted array for testing
test_array = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19];
# Looking for an existing element
result1 = binarysearch(test_array, 7)
println("Searching for item 7: index = $result1") # It should return 4
# Looking for a non-existent element
result2 = binarysearch(test_array, 6)
println("Searching for item 6: index = $result2") # It should return 0
# Looking for the first element
result3 = binarysearch(test_array, 1)
println("Searching for item 1: index = $result3") # It should return 1
# Looking for the last element
result4 = binarysearch(test_array, 19)
println("Searching for item 19: index = $result4") # It should return 10
Conclusion
In this example, we looked at the implementation of the Julia binary search algorithm. We have managed to create an efficient function that can quickly find elements in sorted arrays. The algorithm uses the principle of "divide and conquer", which allows to achieve logarithmic time complexity. . This is especially important when working with large amounts of data, where linear search would be ineffective. The implementation supports generics, which makes it flexible for working with different data types, provided that they support comparison operations.
The example was developed using materials from Rosetta Code