3
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Dawny33 Mar 4 '16 at 7:24
  • 1
    \$\begingroup\$ (Your "backtick-quoting" in the doc comments is inconsistent.) \$\endgroup\$ – greybeard Mar 4 '16 at 9:06
  • \$\begingroup\$ @greybeard Thanks for pointing it out. Would fix in the latest commit :) \$\endgroup\$ – Dawny33 Mar 4 '16 at 9:07
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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 :) \$\endgroup\$ – Dawny33 Mar 4 '16 at 9:29
  • \$\begingroup\$ @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. \$\endgroup\$ – coderodde Mar 4 '16 at 9:36
  • \$\begingroup\$ @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. \$\endgroup\$ – SalchiPapa Mar 4 '16 at 14:10
1
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.