So long as you know where you were last, there's always the sun

Ahem, Ahem! We've got 4 planets!

"Lost at sea" in the eastern Mediterranean is quite a stretch. Wait until dawn, sail south and you will make landfall somewhere in northern Africa within two or three days at most. (And the sky is never overcast in the eastern Med for two days continuously, at least not in the sailing season.) BTW, what do you mean by "compass" and "timepiece" in the "ancient" Mediterranean? Ah, and a "naval" crew in the ancient Med means that you have some kind of galley. Those were built so that they could be drawn on the beach like a boat, so you can sail straight to the shore and ask for directions.

The time and place of the incident in history are important. At least give us some idea of the correct tech level... "ancient" is not a well defined historical term, and being lost in somewhere like the med is (as has been pointed out more than once) very different from being lost in open ocean.

One cloudy night and all is lost? Why are you writing a maritime novel if you know nothing about the subject? Anyhow, this is quite a distance. How do ships usually make that voyage in your world and what is different in this situation other than a cloud? I suspect that clouds are not that exotic in your world. I don't really understand those edits. So they do have a compass? Why can't they hold course and hope that there will be a new day after the night?

So the question should be: I'm writing a novel with the following world I'm building and I don't understand the subject well enough, how and where do I start? That would be a legitimate question imo, a good one in fact. Nobody knows everything. This is currently a bit of a mess because you are attempting step 10 or 11 before completing 1-9 to build a solid foundation first

To be honest, I thought your question was OK, but your successive edits have made it more awkward. Your new requirement, effectively sail the length of Africa with iron-age technology makes it all vastly more difficult and a lot less plausible. If I were you, I'd restore your original question, with original place names, because that will keep the existing answers as valid. You could even accept or upvote some or more of them. Then ask a new question about iron-age navigation of open ocean, tagged reality-check. That's not a bad way to learn something from this site.

I think that I offered honest but constructive criticism and gave you ideas on how to make your question better and explained why your question right now might not give you the answer you want. You seem to have reacted very badly to this. A word of advice: If you are a writer, some people will not like your work and offer criticism. Some of them will have a point. Don't react like that. See the last comment, people don't understand what you want and what you wrote in your question. Fix it please. I told you this question is legitimate if you put in 5 minutes of effort

@ChagatNahn seems fine to me. Hopefully some of the downvoters will re-evaluate their decisions!

Carthage was destroyed by Rome in 146 BC, at the end of the Punic Wars. Mediterranean trade and military expeditions were common by then. Is your naval crew professional sailors of the period, or time travelers who might not know what to do without a compass?

I suggest reading Harry Turtledove's Historical Collection. It is a set of four historical novels, set earlier than you are aiming for, but centered on Mediterranean traders. Turtledove trained as a historian, and would be likely to get the technical details of sea travel right.