The first argument isn't special, though:

  (defmethod binary-search (object (collection Sequence) before?)
    ...)

  (defmethod binary-search (object (collection Vector) before?)
    ...)

...and so on. You could even specialize on everything but the first argument.