One thing you could do is to presort your Lego bricks. Take your giant pile of Lego bricks and try to split it up into 5-10 categories.
Those categories could be color, size, or any other features, it doesn't really matter. (I'm a Technic builder, so I would sort them into axles, pins, pin-connectors, beams and gears for example.) To get the best results these categories should be as close to equal in size.
Presorting might seem to be a bit of work, however next time you need a brick it will be several times faster (roughly equal to the amount of categories) to find it since you only have to look through a subset of bricks. One you have done the presort, you don't need to do it again (until you trow them back into your box) so it makes most sense to do this during a building session where you might need to look after another brick in the near future.
Remember that your piles could contain sub-categories, if you had sorted after color you could use size to skim through the pile in order to find that brick. You could also split those up into even more sub-piles if you wanted. The more you sort, the less time you need to search after bricks, however you will spend more time during your presort. Try to experiment and find a balance between sorting and searching that you like.
In order to not presort more than necessary, do the presorting while you are looking after a brick. Like Pubby suggested, take a small area and look through that. However instead of simply trowing them into a separate pile if you don't find it, sort them into your category piles. Continue this process until you find the brick you were looking for.
Next time you need a brick, look through the incomplete sub-piles first to see if it is there. If not, continue with the giant unsorted pile like before, presorting your bricks until you find the brick.