Search algorithms in julia

Question

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?

Answer 1

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.

Answer 2

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