Binary Search

Question 1

Binary Search algorithm - Recursion O( logn)

Answer 1

int binarySearch(ll a[],ll low,ll high,ll k)
{
    if(low>high)
        return -1;

int mid = (low+high)/2;

if(a[mid]==k)
    return mid;

    if(a[mid]>k)
        return binarySearch(a,low,mid-1,k);

    return binarySearch(a,mid+1,high,k);
}

Question 2

Binary Search algorithm - Iterative O( logn)

Answer 2

int binarySearch(ll a[],ll low,ll high,ll k)
{
    while(low<=high)
    {
        int mid = (low+high)/2;

        if(a[mid]==k)
            return mid;
        else if(a[mid]>k)
            high=mid-1;
        else
            low=mid+1;
    }
    return -1;
}