* a prior art search is not required (that's the PTO's job) but i usually recommend it since it'll save money in the end if there's dead on prior art. it's also required if you want to expedite the process at the PTO.
* you can file for a provisional first then have a year to file a non-provisional based off that.
on your follow up: the time process varies wildly but its in the years time scale (not months or shorter). anecdotally i just gave the PTO a call regarding an application that has been sitting around waiting for an initial response for 2.5 years now, which is somewhat uncommon but not out of the realm of possibility. you can speed up the process, but the PTO charges a rather hefty fee for it.
disclaimer: i AM a patent attorney (and former examiner), but i'm not your attorney!
Have you filed a patent in the past (I assume so)? Do you have any idea how long does it take from submission to obtaining a response?