There are many ways to style this header block. But you don’t need empty clearing divs – ever. At the very least you can accomplish the same thing using the clearfix method which adds a pseudo element and clears that, but that’s all done with css, where the styling should be – not in html, which is where empty clearing elements have no place.
So, you could use the clearfix method, but again giving the header a fixed height is the simplest solution. Barring those two, you could float the logo left with a clear: left; and not float the menu but give it the necessary margin to place it in the right spot.