We actually just moved from South Bay to East Bay. We don't have a car which made getting between the two to look at new places while also working full-time really difficult. We gave up our place in the south bay and found a centrally located sublet in the east bay for a month, rent was the same as on our south bay apartment. We actually wound up being able to line things up really well and only had a couple of days overlap in rent. We did have to rent a uhaul twice but given that our commute costs for the sublet month dropped by about $250 it was worth it (we don't have a lot of stuff so were able to move possessions into the sublet rather than a storage unit...I am so SO grateful to our friends who helped us with the uhaul loading/unloading...worst part of moving and makes me want to get rid of even more stuff).
Anyway, if you have a specific area within the bay area you are looking to live in (city, peninsula, east bay, etc.), I would strongly recommend the route we went, of subletting in the area rather than trying to find somewhere from afar. Rentals on CL move really fast and many landlords/agencies want you to see the place before they will accept an application. Because we were living nearby, we were able to really jump on things as soon as they came up. The place we eventually wound up with we would not even have been able to consider if we had not been nearby, b/c we really would not have been able to see it until the weekend, and the landlady was only available to show it on Wednesday evening. Also, knowing that we had the ability to act fast on the good postings kept us a little more sane and better able to walk away from options that were okay-but-not-really.
I would be a little careful of finding a work-for-cheap living situation if you are also going to be working full-time. Looking for a place to live seriously can be a part-time job in and of itself. If you are thinking you want to find a rental that you can be happy in for several years, it is probably worth paying a bit more in rent for 1-2 months to be able to find it.