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


f(x) = x^2 – 4x -8

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.


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;
	    if ((f(mid)>0) && (mid==low || f(mid-1)<=0))
	    	return mid;
	    else if(f(mid)<=0)
	    	return binarySearch(mid+1,high);
	    	return binarySearch(low, mid-1);
int main()


Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions
Core Java Interview Questions

Wait !!! You can Crack Technical Interviews of Companies like Amazon, Google, LinkedIn, Facebook, PayPal, Flipkart, etc

Anisha was able to crack Amazon after practicing questions from TutorialCup