Since 8.1, you can actually search without going fullscreen by pressing Win+S, which reveals a search sidebar on the right side without bringing up the start screen.