practice

binary_search.cxx

bool find(int* a, int n, int i)
{
    int lo = 0;
    int hi = n-1;
    while (lo <= hi)
    {
        int mid = a[(hi + lo) / 2]; // TODO: Overflow
        printf("lo: %d, mid: %d, hi: %d\n", lo, mid, hi);
        if (mid == i) 
            return true;

        if (mid < i)
            lo = mid + 1;
        else
            hi = mid - 1;
    }
    return false;
}

bool rfind(int* a, int lo, int hi, int i)
{
    if (lo < hi)
    {
        int mid = a[(lo + hi) / 2]; // Overflow!
        if (mid == i)
            return true;
        else if (mid < i)
            return rfind(a, mid + 1, hi, i);
        else
            return rfind(a, lo, mid - 1, i);
    }

    return a[lo] == i;
}

int main()
{
    int n = 1000;
    int* a = new int[n];
    for (int i = 0; i < n; i++) a[i] = i;

    printf("Found: %d\n", rfind(a, 0, n-1, 3));
    printf("Found: %d\n", rfind(a, 0, n-1, 999));
}