When Dumbledore first left Harry in the care of Petunia and Vernon, he invoked powerful protection charms to prevent the Death Eaters from finding Harry's location. At this point, it is assumed that Sirius Black is a Death Eaters. If that is the case, how was Sirius able to find Harry's house when it was supposed to have been protected? As Lily's friend, Sirius might have known the address, but the protection should've been stronger if it was known that Harry's location would be discovered - right?
I recall Dumbledore telling Harry that as long as he was with his kin, he was protected by love - until he would come of age at 17. I do not remember anywhere in canon that said Number 4, Privet Drive was under Fidelius.
It also could not have been protected because Ron had found the house with Fred and George in the beginning of CoS. Harry didn't ever tell Ron or Hermione his home address; he usually referred to it as Privet Drive, as Ron refers to his home as The Burrow, which is not the actual address.
I'm not aware of any answer from canon (books or interviews) but Sirius was one of the Marauders. He'd have known Lily extremely well (being James best friend and Harry's Godfather) and would have likely known that Lily's sister got married and to whom.
Also, I don't recall that Dumbledore actually hid Harry's location - the house wasn't under Fidelius.
Keep in mind that Sirius was not really at Privet Drive 4. Harrys first encounter with him was after he left and was standing on the street. So even if the house was protected, it might just be that he waited until Harry left the house.
Couldn't it be as simple as, the charm was to protect him from Death Eaters, but as he wasn't one, the charm didn't affect Sirius?