Find the point where a monotonically increasing function becomes positive first time

Given a function 'int f(unsigned int x)' which takes a non-negative integer 'x' as the input and returns the value where f() becomes positive for the first time

Example

INPUT:
f(x) = x^2 - 4x -8

OUTPUT:
The value x where f(x) becomes positive is 6

Time Complexity: O(logn)

In this method the main idea is to apply binary search, but for binary search we need low and high values. Below algo shows how to find the values and implement binary search.

Algorithm

1. Till f(i) is greater than zero, double the i value. Once f(i) is greater than zero, then take i as the high and i/2 as the low.

2. Now search for the first positive value of f(i) in between i/2 and i. Binary search

3. Till high greater than or equal to high, find the mid

a. If f(mid) is greater than zero and mid is equal to low or f(mid -1) is less than or equal to     zero ie, f(mid>0) && (mid==low || f(mid-1) <=0), then return mid

b. If f(mid) is less than zero, then search in the right half recursively.

c. If f(mid) is greater than zero, then search in the left half recursively.

C++ Program

#include <bits/stdc++.h>
using namespace std;

int binarySearch(int low, int high);//declaring
//function f(x)
int f(int x)
{
	return x*x - 4*x -8;
}
//prints the value x
void printFirstPositive()
{
	if (f(0) > 0)//if for 0 f(x) >0, then 0 is the answer
	{
		cout<<"The value x where f(x) becomes positive first is 0 "<<endl;
	}
	int i =1;
	//finding low and high for binary search
	while(f(i)<=0) {
	    i = i*2;
	}
	cout<<"The value x where f(x) becomes positive first is "<<binarySearch(i/2,i)<<endl;
}
//binary search implementation
int binarySearch(int low, int high)
{
	int mid = (low + high)/2;
	while(high>=low) 
	{
	    if ((f(mid)>0) && (mid==low || f(mid-1)<=0))
	    {
	    	return mid;
	    }
	    else if(f(mid)<=0)
	    {
	    	return binarySearch(mid+1,high);
	    }
	    else
	    {
	    	return binarySearch(low, mid-1);
	    }
	}
}
int main()
{
	printFirstPositive();
}
Try It

 


Next > < Prev
Scroll to Top