Find the minimum value of a UniModal function
Given a Unimodal Function f(x) = A(x * x) + Bx + C and a range for the value of x in the form of [L, R], the task and is to find the minimum value of f(x) where the value of x can lie in the range [L, R] both inclusive. The minimum value should be accurate up to 6 decimal places.
Note: It is guaranteed that A > 0.
Examples:
Input: A = 2, B = -12, C = 7, L = 6, R = 8
Output: 7
Explanation: For x = 6, f(x) = 2 * (6 * 6) – 12 * 6 + 7 = 7.Input: A = 2, B = -2, C = 8, L = -5, R = 5
Output:
Explanation: For x = 6, f(x) = 2 * (8 * 8) – 12 * 8 + 7 = 39.
Approach: To solve the problem, follow the below idea:
The problem can be solved using Ternary Search as Ternary Search can be used to find the min/max of a Unimodal Function. We can initialize the low of the range as L and high of the range as R. Now, we can take 2 mid points, say mid1 and mid2 and calculate the value of the function at those points. Now according to the value of res1 and res2, we can have 3 cases:
- Case 1: f(mid1) == f(mid2), shift lo = mid1 and hi = mid2
- Case 2: f(mid1) < f(mid2), shift hi = mid2
- Case 3: f(mid1) > f(mid2), shift lo = mid1
Keep on reducing the range till we reach our answer.
Step-by-step algorithm:
- The f function calculates the value of the quadratic expression Ax^2 + Bx + C for a given value of x.
- Ternary search is used to find the minimum of a unimodal function within a given range [l, r].
- The ternary search algorithm divides the range into three parts and eliminates one-third of the search space in each iteration.
- The function compares the values at two points (mid1 and mid2) within the range and updates the search space accordingly.
- The process continues for 200-300 iterations as this guarantees that the the search space has been reduced ans is now accurate up to 6 decimal places.
- The result is printed as the f(l) or f(r).
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h> using namespace std; double a, b, c; // calculate the value of the given quadratic expression // ax^2 + bx + c double f( double a, double b, double c, double x) { // The quadratic function: ax^2 + bx + c return a * x * x + b * x + c; } // Ternary search algorithm to find the minimum of a // unimodal function within a given range [l, r] double ternary_search( double l, double r) { int cnt = 300; while (cnt--) { double mid1 = l + (r - l) / 3.0; double mid2 = r - (r - l) / 3.0; // Compare function values at mid1 and mid2 to // determine the search range if (f(a, b, c, mid1) < f(a, b, c, mid2)) r = mid2; else l = mid1; } return f(a, b, c, l); } int main() { // Driver code a = 2, b = -2, c = 8; double l, r; l = -5, r = 5; cout << fixed << setprecision(7) << ternary_search(l, r); return 0; } |
Java
import java.text.DecimalFormat; public class TernarySearch { static double a, b, c; // Calculate the value of the given quadratic expression // ax^2 + bx + c static double f( double a, double b, double c, double x) { // The quadratic function: ax^2 + bx + c return a * x * x + b * x + c; } // Ternary search algorithm to find the minimum of a // unimodal function within a given range [l, r] static double ternarySearch( double l, double r) { int cnt = 300 ; while (cnt-- > 0 ) { double mid1 = l + (r - l) / 3.0 ; double mid2 = r - (r - l) / 3.0 ; // Compare function values at mid1 and mid2 to // determine the search range if (f(a, b, c, mid1) < f(a, b, c, mid2)) r = mid2; else l = mid1; } return f(a, b, c, l); } public static void main(String[] args) { // Driver code a = 2 ; b = - 2 ; c = 8 ; double l, r; l = - 5 ; r = 5 ; DecimalFormat df = new DecimalFormat( "#.#######" ); System.out.println(df.format(ternarySearch(l, r))); } } // This code is contributed by shivamgupta310570 |
Python3
# Calculate the value of the given quadratic expression # ax^2 + bx + c def f(a, b, c, x): # The quadratic function: ax^2 + bx + c return a * x * x + b * x + c # Ternary search algorithm to find the minimum of a # unimodal function within a given range [l, r] def ternary_search(l, r): cnt = 300 while cnt > 0 : mid1 = l + (r - l) / 3.0 mid2 = r - (r - l) / 3.0 # Compare function values at mid1 and mid2 to # determine the search range if f(a, b, c, mid1) < f(a, b, c, mid2): r = mid2 else : l = mid1 cnt - = 1 return f(a, b, c, l) # Driver code a, b, c = 2 , - 2 , 8 l, r = - 5 , 5 print ( "{:.7f}" . format (ternary_search(l, r))) |
C#
using System; public class MainClass { static double a, b, c; // Calculate the value of the given quadratic expression // ax^2 + bx + c static double F( double x) { // The quadratic function: ax^2 + bx + c return a * x * x + b * x + c; } // Ternary search algorithm to find the minimum of a // unimodal function within a given range [l, r] static double TernarySearch( double l, double r) { int cnt = 300; while (cnt-- > 0) { double mid1 = l + (r - l) / 3.0; double mid2 = r - (r - l) / 3.0; // Compare function values at mid1 and mid2 to // determine the search range if (F(mid1) < F(mid2)) r = mid2; else l = mid1; } return F(l); } public static void Main( string [] args) { // Driver code a = 2; b = -2; c = 8; double l, r; l = -5; r = 5; Console.WriteLine($ "{TernarySearch(l, r):F7}" ); } } |
Javascript
let a, b, c; // Function to calculate the value of the given quadratic expression ax^2 + bx + c function f(a, b, c, x) { // The quadratic function: ax^2 + bx + c return a * x * x + b * x + c; } // Ternary search algorithm to find the minimum of a unimodal function within a given range [l, r] function ternarySearch(l, r) { let cnt = 300; while (cnt--) { let mid1 = l + (r - l) / 3.0; let mid2 = r - (r - l) / 3.0; // Compare function values at mid1 and mid2 to determine the search range if (f(a, b, c, mid1) < f(a, b, c, mid2)) r = mid2; else l = mid1; } return f(a, b, c, l); } // Driver code a = 2, b = -2, c = 8; let l = -5, r = 5; console.log(ternarySearch(l, r).toFixed(7)); |
7.5000000
Time Complexity: O(2 * log3(N)), where N is the range of [L, R].
Auxiliary Space: O(1)
Contact Us