There should be no problem just walking into a suitable place in Madrid if you stick to the Sol/Santa Ana/Plaza Mayor areas. Its often better than booking ahead as you can see a selection of rooms before choosing the one you like best if you dont mind half an hour's door knocking. Other advantage is you can haggle for a discount too. Try Hotel Santander on c/de Echegaray, who we got down to 55 euros from 65.