how isKey searches keys of an associative map (containers.Map)

If M is an associative map (containers.Map) and k is a potential key, what exactly happens when I execute isKey(M,k)? It seems that the output of keys(M) is ordered by whatever the "natural" order is for M's particular type of key. Does that mean that isKey does a binary search? Or does isKey do a linear search? Or does isKey do something else? Or does it depend on details that I didn't include here?

Thanks!