My sympathies to the OP. I am curious to know what the rocket and motor were. It sound like a too-large motor was used for first flight, but there are a lot of other variables in play as well.
Here are a few True Facts about this hobby, some of which overlap what others have said.
1) Losing rockets sucks.
2) Losing your first rocket on your first flight sucks extra hard.
3) If you fly rockets, at some point you will lose one, for any of a variety of reasons. Doesn't matter how experienced you are, or how carefully you plan. Couple of years ago I watched an experienced rocketeer launch a gorgeously built high powered rocket perfectly straight upward through the wispy clouds, never to be seen again. No one saw it come down (it's amazing how that can happen), and the tracker failed. I still shudder at that one.
3b) A corollary to the above is that you should never fly what you're not willing to lose. This is actually a standard rocketry maxim. Presumably applies to flying RC planes as well, although they're probably not as often completely lost as destroyed.
4) That said, with careful planning you can minimize the chance of losing your rockets.
5) A philosophy that I and many others go by is: "It isn't a rocket until it flies". I will fly everything I build at least once, no matter how many hours spent on construction and finishing. That doesn't mean I won't be puckering like crazy, and I absolutely do not want to lose any of them (some more than others, certainly). I will do everything in my power to plan the flight so I'll get it back, but I know there are no guarantees. That, I suppose, is part of the "excitement" of launching.
In addition to proper flight planning (knowing how high your rocket will go with the motor your using, having a good idea of the wind, knowing your recovery area), there are a few other things you can do:
1) Build up a small fleet of rockets to bring when you fly. This will reduce the sting of losing one.
2) Always have a couple of rockets that you don't care much about (ready-to-fly rockets work great for this), and fly at least one of them first on a small motor. This way you can gauge the winds and make better motor choices on your subsequent flights. If the results of the flight are not good (e.g., long drift), you might choose to fly nothing but those "disposable" rockets on that day.
3) *Most* rockets can be flown on a small enough motor that it'll come down fairly close and can be recovered. Exceptions are tiny light rockets like the Mosquito, tend to disappear once they get up there, and which can be hard to find even if they land right next to you.
4) Advice given above about having other folks with you to help track the rockets is very helpful. This is one of many advantages of flying with a club: lots more eyes to help track the rockets coming down.
None of this takes away the sting when you inevitably lose one. However, unless you're really foolish, over time your percentage of lost rockets will be small. An in any case, if you enjoy the building of the rocket, then it's hardly pointless.