Yes, it's correct and common in both writing and speech. The part in parentheses helps you, the learner, understand the sentence a little better. The part "trying to find Alex's house" is called a participle phrase. Basically, it can't stand by itself, but must connect with some part of the previous clause (in this case, "got lost"). It differs from a noun clause (which starts with a gerund... which looks exactly like a participle...) because a noun clause functions as a thing in the sentence. Look at the word order and you'll see that the phrase "trying to find..." doesn't work as a noun, but only offers extra information instead.

Yes it is quite common in grammar books because they do this to give you more information so that you can understand and compare the sentence. I am quite sure that this sentence came from a grammar book because you would not usually see this anywhere else.

Thanks all.

Yes and yes.

I got lost trying to find Alex's house. I got lost when I was trying to find Alex's house. Both are correct. Yea, both are correct. :)