Can we use ternary search to find the optimal value for the polynomial degree and the regularization parameter?

Here, prof. Andrew shows the shape of the curve for the cross-validation error for different degrees of a polynomial model, and also for the regularization parameter.

The curve here looks like a unimodal function for both curves.

Ternary search is an algorithm that is used to find the minimum (or the maximum) of a unimodal function.

Aside from the fact that training models on different parameters is not cheap, and that this idea might take so long, on an abstract level, is it correct?

In concept that seems possible. A ternary search is fairly efficient, and may be be a useful way to find the minimum of the Jcv vs lambda curve.

If you try it, please post back your results.

Finding precisely the optimum lambda is often not critical - just getting close is usually sufficient.