Binary Search

public class Solver
{
    public static void main(String args[])
    {

    }

    public static boolean binary_serach(int a[], int l, int r, int target)
    {
        if (l > r)return false;
        if (l == r)return a[l] == target;
        int mid = (l + r) >> 1;
        if (target == a[mid])return true;
        if (a[mid] > target)return binary_serach(a, l, mid - 1, target);
        else return binary_serach(a, mid + 1, r, target);
    }

    public static int lower_bound(int a[], int l, int r, int target)
    {
        if (l > r)return -1;
        if (l == r)
        {
            if (a[l] >= target)return a[l];
            return -1;
        }
        int mid = (l + r) >> 1;
        if (a[mid] >= target)return lower_bound(a, l, mid, target);
        else return lower_bound(a, mid + 1, r, target);
    }

    public static int upper_bound(int a[], int l, int r, int target)
    {
        if (l > r)return -1;
        if (l == r)
        {
            if (a[l] > target)return a[l];
            return -1;
        }
        int mid = (l + r) >> 1;
        if (a[mid] > target)return upper_bound(a, l, mid, target);
        else return upper_bound(a, mid + 1, r, target);
    }
}