We’re given a function in the format of f(x). We have to find the minimum absolute difference between f(x) and given number k over a range (0 – 10^6).
This article assumes you know the working principle of binary search. If you don’t know, please go and check out the binary search.
To understand this concept, let’s assume a function f(x) such that:
f(x) = e^x
We have to find the value of x such that the absolute difference of f(x) and some given number k is minimum.
The naive approach would be to iterate over the range and check each value which is closest to k. Which would take O(n).
The efficient approach is to modify the binary search to get the answer, and the time complexity of this approach is O(logn), which is much better for a larger range (i.e., 10^18).
Examples:
Input : 100 Output : 4 The closest value to 100 f(x) reaches is at x = 4, which is 54.59 Input : 500 Output : 6 The closest value to 500 f(x) reaches is at x = 6, which is 403.42
Implementation:
CPP
#include <bits/stdc++.h>
double func(int x) // Function returning e^x
{
return exp(x);
}
int modified_binary_search(int low, int high, int k)
{
int mid;
double min_diff = INT_MAX; // Variable to store the minimum difference
int ans = -1;
while (low <= high)
{
mid = low + (high - low) / 2;
if (std::abs(func(mid) - k) < min_diff)
{
ans = mid;
min_diff = std::abs(func(mid) - k);
}
if (func(mid) < k)
{
low = mid + 1;
}
else
{
high = mid - 1;
}
}
return ans;
}
int main(void)
{
int k = 500;
int low = 0, high = 1e6; // Range to look for x;
int ans = modified_binary_search(low, high, k);
std::cout << ans;
return 0;
}
Python3
from math import exp
INF = 1e8
def func(x):
return exp(x)
def modified_binary_search(low, high, k):
min_diff = INF
ans_temp = -1
while low <= high:
mid = int(low + (high - low) / 2)
if abs(func(mid) - k) < min_diff:
ans_temp = mid
min_diff = abs(func(mid) - k)
if func(mid) < k:
low = mid + 1
else:
high = mid - 1
return ans_temp
def main():
k = int(500)
low = int(0)
high = int(1e3)
ans = modified_binary_search(low, high, k)
print(ans)
if __name__ == "__main__":
main()
Output: 6