implementation of lower_bound() and upper_bound()

lower bound: is used to return an iterator pointing (index) to the first element in the given range which has a value greater than or equal to the given value.

upper bound: which returns an iterator pointing (index) to the first element in the given range which is greater than the given value. 

Example: Lower bound index

Input:  arr = { 4, 3, 2, -1 }, lower =0
Output: 1

Example: Upper bound index

Input:  arr = { 4, 3, -2, -1 }, upper =0
Output: 2

Approach: Lower Bound index

Java 

import java.util.Arrays;

public class LowerBound {
    public static void main(String[] args) {
        int[] arr = { 4, 3, 2, -1 };
        int lower = 0;
        System.out.println(lowerBound(arr, lower));
    }

    public static int lowerBound(int[] arr, int k) {
        // sort the array in ascending order
        Arrays.sort(arr);
        int low = 0;
        int high = arr.length;
        while (low != high) {
            //calculate mid point
            int mid = low + (high - low) / 2;
            if (arr[mid] < k) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }

        return low;
    }
}

C++

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



int lowerBound(int arr[], int n,int k) 
{
    //sort the array in ascending order
    sort(arr,arr+n);
    int low =0;
    int high =n;
    while(low != high) 
    {
        //calculate mid point
        int mid = low + (high - low) / 2;
        if (arr[mid] < k) {
                low = mid + 1;
            } else {
                high = mid;
            }
     }

    return low;
}

int main()
{
    int arr[] ={4,3,2,-1};
    int lower = 0;
    int n=sizeof(arr)/sizeof(arr[0]);
    cout<<lowerBound(arr, n,lower);
    return 0;
}

Approach: Upper Bound index

Java 

import java.util.Arrays;

public class UpperBound {
    public static void main(String[] args) {
        int[] arr = { 4, 3, -2, -1 };
        int upper = 0;
        System.out.println(upperBound(arr, upper));
    }

    public static int upperBound(int[] arr, int k) {
        // sort the array in ascending order
        Arrays.sort(arr);

        int low = 0;
        int high = arr.length;
        while (low != high) {
            // calculate mid point
            int mid = low + (high - low) / 2;
            if (arr[mid] <= k) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }
}

C++

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



 int upperBound(int arr[], int n,int k) 
 {
        // sort the array in ascending order
        sort(arr,arr+n);
        int low = 0;
        int high = n;
        while (low != high) {
            // calculate mid point
            int mid = low + (high - low) / 2;
            if (arr[mid] <= k) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
}
int main()
{
    int arr[] = { 4, 3, -2, -1 };
    int upper = 0;
    int n=sizeof(arr)/sizeof(arr[0]);

    cout<<upperBound(arr, n,upper);
    return 0;
}