Does this need to be "Visitor Level"? Or within a Visit?
If you are looking at Visitor, this could be a very large number because it will include all the visits that the user didn't even perform a search (plus, if the user did multiple searches, I don't know if there is a proper way to only include since the last search, or at least it won't be easy)
In both cases though, this would require a sequential segment.
But there will be variations depending on how you record a "search being made"... if you have an event on an action (search submit form) vs identifying a search by landing on a search results page.... I have both, so I am going to add some extra logic to my example to make sure that the segment does bring back extra data)
VISIT (Only Before Sequence)
[HIT level Container]
Page Views exists
Page Type (prop/eVar) does not equalsearch
THEN within 1 hit
Search Performed (event) exists
Essentially, I am looking for any non-search page view followed directly by a "search performed" event, and only looking at traffic with a visit up until this sequence (please note that the Only Before Sequence is a bit odd.. it's not really before it's before and including the sequence)
If you don't have a "Search Performed" event, you should be able to do a modified: