/*
 * Search for integer a in sorted array arr[n] similarly to Newton's method
 */
int newtonsearch(int *arr, int n, int a)
{
    int i = 0;
    while (i >= 0 && i < n && arr[i] != a) {
        i -= arr[i] / (arr[i + 1] - arr[i]); // TODO check for boundary conditions, zero denominator, rounding errors
    }
    return i >= 0 && i < n ? i : -1;
}

/*
 * Regular binary search on sorted array, analogous to interval cutting for numerical optimization
 */
int binsearch(int *arr, int n, int a)
{
    int max = n - 1, min = 0, mid;
    for (mid = max / 2; min < max && arr[mid] != a; mid = (max + min) / 2) {
        if (arr[mid] > a)
            min = mid;
        else
            max = mid;
    }
    return arr[mid] == a ? mid : -1;
}