Question

Given a monotonically increasing function f(n) (where ‘n’ is an integer), use a binary search algorithm to find the largest value of ‘n’ for which f(n) is less than a target. Show all the work (including the values for the left index, right index, middle index and the function value at the middle index) for each iteration as well as write down the initial values of the left index and right index and the corresponding function values.

f(n) = 3n^3 + 5n + 1, Target = 100

Answer 1

First we have to find the upper limit to apply binary search. the largest value of n where it becomes greater than =100. this can done in O(logn) time complexity as shown in the below function:

We do repeated doubling of n until f(n)>=100;

int findLargestNumber()

{

    if (f(0) >= 100)

        return 0;

    int i = 1;

    while (f(i) < 100)

        i = i*2;

    return binarySearch(i/2, i);

}

Next we do binary Search

.................................

int binarySearch(int low, int high)

{

    if (high >= low)

    {

        int mid = low + (high - low)/2;

         cout<<"Left Index: "<< low<<endl;

     cout<<"Right Index: "<< high<<endl;

     cout<<"Mid Index: "<<mid<<endl;

     cout<<"............."<<endl;

        if (f(mid) < 100 && (mid == low || f(mid+1) >= 100))

            return mid;

        if (f(mid) < 100)

            return binarySearch((mid + 1), high);

        else

            return binarySearch(low, (mid -1));

    }

    return -1;

}

The Complete C++ Code is:

..................................

#include<bits/stdc++.h>

using namespace std;

int binarySearch(int low, int high);

int f(int x) { return (3*x*x*x + 5*x +1); }

int findLargestNumber()

{

    if (f(0) >= 100)

        return 0;

    int i = 1;

    while (f(i) < 100)

        i = i*2;

    return binarySearch(i/2, i);

   

}

int binarySearch(int low, int high)

{

    if (high >= low)

    {

        int mid = low + (high - low)/2;

         cout<<"Left Index: "<< low<<endl;

     cout<<"Right Index: "<< high<<endl;

     cout<<"Mid Index: "<<mid<<endl;

     cout<<"............."<<endl;

        if (f(mid) < 100 && (mid == low || f(mid+1) >= 100))

            return mid;

        if (f(mid) < 100)

            return binarySearch((mid + 1), high);

        else

            return binarySearch(low, (mid -1));

    }

    return -1;

}

int main()

{

    cout<<"The value n where f() becomes" <<

        ">=100 "<< findLargestNumber();

    return 0;

}