My company recently switched to Lync for our internal communications and thus far its been great. Unfortunately despite all of our domain DNS settings being set-up perfectly, the Lync app on Android doesn’t seem to be able to auto-discover its settings.
It turns out however that all you need other than your office 365 email address and password is the following two settings (everything else can be left blank):
Internal discovery address: http://webdir.online.lync.com/Autodiscover/autodiscoverservice.svc/Root
External discovery address: http://webdir.online.lync.com/Autodiscover/autodiscoverservice.svc/Root