# Search algorithms in julia

I've been trying to implement the basic search algorithms: Sequential search for ordered and unordered arrays and the binary search algorithms, as part of a package.

So, this is the implementation:

"""
seqsearch{T}(x::AbstractArray{T}, item::T) ↦ found::Bool
Searches for an item using the **Sequential Search** approach.
"""
function seqsearch{T}(x::AbstractArray{T}, item::T)
index = 1
found = false

while index <= length(x) && !found
x[index] == item ? found = true : index += 1
end

return found
end

"""
ordseqsearch{T}::(x::AbstractArray{T}, item::T) ↦ found::Bool
Searches for an item in a sorted array using the **Sequential Search** approach.
"""
function ordseqsearch{T}(x::AbstractArray{T}, item::T)
index = 1
found = false
stop  = false

while index <= length(x) && !found && !stop
x[index] == item ? found = true : x[index] > item ? stop = true : index += 1
end

return found
end

"""
binarysearch{T}::(x::AbstractArray(T), item::T) ↦ found::Bool
Searches for an item in a sorted array using the **Binary Search** algorithm
"""
function binarysearch{T}(x::AbstractArray{T}, item::T)
first = 1
last = length(x)
found = false

while first <= last && !found
middle = fld(first+last, 2)

if x[middle] == item
found = true
else
if item > middle
first = middle + 1
else
last = middle - 1
end
end

end

return found
end


I want to make the implementations as fast as possible, with as less dependencies as possible.

So, are there any ways to make it cleaner (and/or) faster?

• I didn't use the ? : construct for the if else in the binary search implementations, as I felt it'd be very long and confusing. Mar 4, 2016 at 7:24
• (Your "backtick-quoting" in the doc comments is inconsistent.) Mar 4, 2016 at 9:06
• @greybeard Thanks for pointing it out. Would fix in the latest commit :) Mar 4, 2016 at 9:07

I would get rid of variables found and stop, and just return true on match, false after the body (which means there was no match). The reason is that you keep checking in the loop conditional their value; that's unnecessary computation.

Edit Actually, it would be even better if you returned the index of the found element instead of just a boolean value indicating whether the element is in the input array. In case there is no match, return a value that cannot be a valid array index, for example, -1.

• Initially, my idea was to return a tuple like this (Boolean, element), then I went ahead with just returning the Boolean value. Maybe I should reconsider :) Mar 4, 2016 at 9:29
• @Dawny33 In Julia, is there some None keyword à la Python? If yes, you could return an index on match, and that very None on failure. Mar 4, 2016 at 9:36
• @coderodde there is nothing of type Void, but that would make the function type unstable (could be Void or Int,ie: Union{Void, Int} see @code_warntype macro), you could either return 0 or -1 as you mention or a Nullable{Int} for it to be type stable and performant. Mar 4, 2016 at 14:10

Possibly this code is more readable? It just skips elements which are too small (and stops iteration either on an element sought, a too big element or at the list's end) then tests if the right element is found.

function ordseqsearch{T}(x::AbstractArray{T}, item::T)
index = 1

while index <= length(x) && x[index] < item
index += 1
end

return index <= length(x) && x[index] == item
end