cmd/search: mark installed formulae

`brew search emacs`, with homebrew/emacs tapped:
```
real    0m2.586s
user    0m1.138s
sys     0m0.121s
```
Previously:
```
real    0m2.831s
user    0m1.385s
sys     0m0.087s
```

`brew search s`:
```
real    0m2.260s
user    0m1.201s
sys     0m0.114s
```

Previously:
```
real    0m5.953s
user    0m4.827s
sys     0m0.226s
```

Closes Homebrew/homebrew#35696.
Closes Homebrew/homebrew#42662.

1 files changed, 8 insertions, 3 deletions

diff --git a/Library/Homebrew/cmd/search.rb b/Library/Homebrew/cmd/search.rb
index ba2932450..928ba9d7c 100644
--- a/Library/Homebrew/cmd/search.rb
+++ b/Library/Homebrew/cmd/search.rb
@@ -143,10 +143,15 @@ module Homebrew
     aliases = Formula.aliases
     results = (Formula.full_names+aliases).grep(rx).sort
 
-    # Filter out aliases when the full name was also found
-    results.reject do |name|
+    results.each_with_index do |name, i|
       canonical_name = Formulary.canonical_name(name)
-      aliases.include?(name) && results.include?(canonical_name)
+      # Remove aliases from results when the full name was also found
+      if aliases.include?(name) && results.include?(canonical_name)
+        results.delete_at(i)
+      # Notify the user if the formula is installed
+      elsif (HOMEBREW_CELLAR/canonical_name).directory?
+        results[i] = "#{name} (installed)"
+      end
     end
   end
 end