Hi kk
DO you get any accomdation as soon as u land in germany?
If so, u can search after coming here and have a look at following websites.
If you can get a house thru agent you need to pay some amount to him and 3months rent advance to owner(I am not sure wether it is nearly 18% of the rent excluding maintenance charges)
If you can get a house without agent you need to pay only 3months advance to owner.
lastly it depends up on the owner wether he should be informed before 3months of leaving the house or more than that or less than that.
In germany as per rule it is min 3months.
you can go thru
www.Immobilienscout24.de
any doubts you can ask.....without hesitating