🔍 Ternary Search – Complete In-Depth Explanation

Ternary search is a search algorithm used to find the maximum or minimum value of a unimodal function (a function with a single peak or trough). It's similar to binary search but divides the search space into three parts instead of two.

📌 Why is Ternary Search Important?

💡 Efficiently finds the extremum of unimodal functions.
⚙️ Useful in optimization problems.
🚀 Faster than linear search for certain functions.

📌 Understanding Ternary Search with an Example

Let's say we have a unimodal function f(x) and we want to find its maximum value within a given range [left, right]. Ternary search works as follows:

Divide the interval [left, right] into three equal parts:

mid1 = left + (right - left) / 3
mid2 = right - (right - left) / 3

Evaluate the function at mid1 and mid2: f(mid1) and f(mid2).
If f(mid1) < f(mid2), the maximum must be in the interval [mid1, right]. So, set left = mid1.
If f(mid1) > f(mid2), the maximum must be in the interval [left, mid2]. So, set right = mid2.
Repeat steps 1-4 until the interval [left, right] becomes sufficiently small (within a desired tolerance).

Imagine finding the peak of a hill. You test at two points. If the point on the right is higher, you know the peak must be to the right of the left test point. If the left point is higher, you know it's to the left of the right test point.

🔹 Key Points

Works only for unimodal functions.
Divides the search space into three parts.
Repeatedly narrows down the interval.

🛠 Solution Approach


                  #include 
                  #include  // For setting precision
              
                  using namespace std;
              
                  // Example unimodal function (replace with your actual function)
                  double f(double x) {
                      return -x * x + 10 * x + 5; // Example: a parabola with a maximum
                  }
              
                  double ternarySearch(double left, double right, double tolerance = 1e-6) {
                      while (right - left > tolerance) {
                          double mid1 = left + (right - left) / 3;
                          double mid2 = right - (right - left) / 3;
              
                          if (f(mid1) < f(mid2)) {
                              left = mid1;
                          } else {
                              right = mid2;
                          }
                      }
                      return (left + right) / 2; // Return the approximate x-value of the extremum
                  }
              
                  int main() {
                      double left = 0;
                      double right = 10;
              
                      double result = ternarySearch(left, right);
              
                      cout << fixed << setprecision(6); // Set precision for output
                      cout << "Maximum value found at x = " << result << endl;
                      cout << "f(x) = " << f(result) << endl;
              
                      return 0;
                  }

⏳ Time Complexity Analysis

The time complexity of ternary search is O(log₃ n), which is approximately O(log n). It's slightly slower than binary search, but still logarithmic.

🌍 Real-World Applications of Ternary Search

⚙️ Optimization problems (finding the best parameters).
📈 Finding the peak of a curve.
🤖 Machine learning (tuning hyperparameters).