First, contacts are not backed up to icloud when you perform an icloud backup, because they already live in their own database on icoud.
iCloud maintains a database of your contacts which it uses to keep all devices and computers connected to the same iCloud account in sync. If you ever wonder whether you've lost contacts because they do not appear on a device or mac/pc, you should log into iCloud.com using a computer's browser and go to the Contacts page. You should find your contacts there. If there but they do not appear on your device, see below for instructions. If they are not there, then for one reason or another, they have been deleted. See below for options if this is the case.
Getting contacts from iCloud to a device.
Your device/computer needs to be connected to the proper account in iCloud and have contacts set for syncing. Go to Settings>iCloud (for a device) or System Preferences>iCloud (for a mac - can't help you with a PC, but hopefully you'll know where to go). Be sure iCloud is turn on and that you have the right account. If you need to change the account, scroll to bottom of screen (device) and tap Delete Account. Find a similar button on a mac. This will not delete data from iCloud, it only disconnects the device/mac from the current account. Then enter ID/password for the correct account. Next, be sure Contacts is turned on. [If it has been turned on, try turning off and then back on. If still not working, disconnect from iCloud and connect again.] You should get your contacts back.
Contacts are gone from icloud.com.
Then they have been deleted. There are many reasons for this. One possibility is that someone else is using the same iCloud account (family member, etc.) and they deleted contacts, thinking they did want them on THEIR device. How to get them back? Unfortunately, an iCloud backup does not include any of the sync databases, like contacts, notes, calendars, reminders, etc. because the data is already stored in these databases. Your only hope for restoring the data is if you had that data on a computer (like a mac's Contacts, Calendars, etc.) and that data was backed up using whatever backup software you typically use (e.g. Time Machine on a mac). Just restore the data files back to the computer. Other than that, I'm afraid the data is gone.
iCloud doesn't sync with Google contacts. You sync your Google contacts by setting up your gmail account as an exchange account, then turn on contacts (and turn off contacts in Settings>iCloud as you won't be syncing your contacts with iCloud). This article explains how to set this up: http://support.google.com/mail/bin/answer.py?hl=en&answer=138740.