Binary Search Lower Bound and Upper Bound

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

int ar[N+5];

int lowerBound(int itm , int sz)
{
    int lo=0, hi=sz-1 , mid;

    while(lo <= hi)
    {
        mid = (lo + hi) / 2 ;

        if(ar[mid] == itm)
        {
            hi = mid-1;
        }

        else if(ar[mid] > itm)
        {
            hi = mid-1 ;
        }

        else if(ar[mid] < itm)
        {
            lo = mid+1;
        }
    }

    return lo;
}

int upperBound(int itm, int sz)
{
    int lo=0, hi=sz-1, mid;

    while(lo <= hi)
    {
        mid = (lo+hi) / 2;

        if(ar[mid] == itm)
        {
            lo = mid+1;
        }

        else if(ar[mid] > itm)
        {
            hi = mid - 1;
        }

        else if(ar[mid] < itm)
        {
            lo = mid+1;
        }
    }

    return lo;
}

int main()
{
    int n;

    cout << "Take array size: ";

    while(cin >> n)
    {
        int i;

        for(i=0;i<n;i++)
        {
            cin >> ar[i];
        }

        int q;
        cout << "Number of Query: ";
        cin >> q;

        while(q--)
        {
            int x;
            cin >> x;

            int lw,up;

            lw = lowerBound(x,n);

            cout << "index = " << lw << " value = " << ar[lw] << "\n";

            up = upperBound(x, n);

            cout << "index = " << up << " value = " << ar[up] << "\n";
        }

        cout << "Take array size: ";
    }

    return 0;
}

Cube Root - Binary Search - Bisection Method

// Cube root
// Binary Search-Bisection Method

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

#define out(x) cout << x << "\n"
#define sf scanf
#define pf printf
#define ex 1e-6

typedef long long LL;

double diff(double n, double mid)
{
    if(n > (mid * mid *mid)) return n - (mid * mid *mid);
    else return (mid * mid *mid) - n;
}

double bisection(double n)
{
    double lo=0.0, hi=n, mid=0.0;

    while(true)
    {
        mid = (lo + hi) / 2.0;

        double d = diff(n,mid);

        if(d <= ex) return mid;

        if((mid * mid * mid) > n) hi = mid;
        else lo = mid;
    }
}

int main()
{
    double x;
    while(cin >> x)
    {
        cout << "Cube root of " << x << " is " << bisection(x) << "\n";
    }

    return 0;
}

Find the power by O(lgn)

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

#define out(x) cout << x << "\n"

// O(n) solution

//int power(int x, int y)
//{
//    if(y == 0) return 1;
//
//    if(y % 2 == 0)
//    {
//        int r = power(x, y/2);
//        return r*r;
//    }
//
//    else
//    {
//        return x * power(x, y/2) * power(x, y/2);
//    }
//}
//
//int main()
//{
//    int x,y;
//
//    while(cin >> x >> y)
//    {
//        cout << power(x, y) << "\n";
//    }
//}


// O(lgN) Solution

// when y is positive
// the function can be optimized to O(logn) by calculating power(x, y/2) only once and storing it.

//int power(int x, int y)
//{
//    int temp;
//
//    if(y == 0) return 1;
//
//    temp = power(x, y/2);
//
//    if(y % 2 == 0) return temp * temp;
//
//    else
//    {
//        return x * temp * temp;
//    }
//}
//
//int main()
//{
//    int x,y;
//
//    while(cin >> x >> y)
//    {
//        cout << power(x, y) << "\n";
//    }
//}


// O(lgn), when y is negative

float power(int x, int y)
{
    float temp=0.0;

    if(y == 0) return 1;

    temp = power(x, y/2);

    if(y % 2 == 0) return temp * temp;

    else
    {
        if(y > 0) return x * temp * temp;

        else
        {
            return temp * temp / x;
        }
    }
}

int main()
{
    int x,y;

    while(cin >> x >> y)
    {
        cout << power(x, y) << "\n";
    }
}