There are a lot of hotels in Bali and Lombok, so I think you will be fine without booking in advance. However, I would recommend that you do otherwise, unless you're willing to take the first hotel you see. I once did this in Jogjakarta (no booking) and won't do it again. It's a waste of time, going from one hotel to another to find the best price.

Searching online is more comfortable. You get to see pictures and read reviews from other people. Not all hotels are advertised online though (especially the cheap ones), but within your budget, you should get quite a lot of options in internet. As Willeke pointed out, there are rooms with no or low cancellation cost (until a couple of days before arrival). I went to Lombok and Sumbawa last January and booked all hotels in advance.

**UPDATE**

I read the other answer and decided to put my comment here.
Pictures can be different, that's why I recommend to book only from trustworthy websites and always read the reviews. If there is no review yet, google it. If you don't book in advance, always ask to see the room first before paying, especially if the hotel is small. Yes, ripping off happens, even to me as an Indonesian. Try to get an idea of the ideal price before doing anything. Be careful and I hope you enjoy your trip!