I was playing in a rec. league last night and after a made shot I proceed to inbound the ball by stepping 1 foot out and the other foot lifted in the air so I was straddling the line with 1 foot out and the other in the air.
One of the official tells me to be legally out of bound which I thought I was when I step out and nothing else was touching the playing court, so he gave me an warning for it when I did it again, so when I ask him the ruling on that, he said that I had to be completely across the boundary line.
Can anyone tell me where in the rule book that say that?

I think he was wrong based upon your description of play--as long as your one foot was completly out of bounds and the other in the air (not touching in bounds) i think you were ok

You were OOB as per rule 4-35-1 & 2. During your throw-in, you did not commit any of the violations listed in rule 9-2. Ergo, legal throw-in. The other official was wrong.