第十二天

小明今天要挑战一下算法！他的算法第一课是：二分查找。

小明随意设置了一个函数：\(y=x^2+2x-1，x\in(-10^4, 10^4)\)。他将使用二分法，找出给出的数字所在区间，精度为\(\pm1\)。

输入

程序运行时通过scanf获取一个整型，作为给定数。

输出

打印给定数所在函数区间，精度为\(\pm1\)。若给定数有不只一个解，打印任意一个区间即可；若给定数恰好被二分查询到，直接打印对应的\(x\)值即可；若给定数不在值域内，请打印error。

样例

Input a number:1
 (0, 1)

Input a number:100019999
 10000

Input a number:-1
 0

Input a number:-4
 error

关键

算法基础

提示

“二分法”相关链接：二分法一文全搞定

解析

#include <stdio.h>
#include <iso646.h>


int func(int x);

void dichotomy(int target, int lo, int hi, int is_increment);

int main() {
    int y;
    printf("Input a number: ");
    scanf("%d", &y);

    // 由于在定义域里， f(x) 并非单调函数，我们应该手动判断区间。
    if (y < -2) {
        dichotomy(y, -10001, 0, 0);
    } else if (y == -2) {
        printf("-1\n");
    } else {
        dichotomy(y, -2, 10001, 1);
    }

    return 0;
}


int func(int x) {
    return x * x + 2 * x - 1;
}


/**
 * @brief              : 二分查找 target = func(x), x in (lo, hi); 将结果打印出来
 * @param target       : 目标值
 * @param lo           : 范围较小值
 * @param hi           : 范围较大值
 * @param is_increment : 函数是否递增
 */
void dichotomy(int target, int lo, int hi, const int is_increment) {
    int x, y;

    // 判断数字是否合理
    if (is_increment) {
        if (func(lo) > target or func(hi) < target) {
            printf("error");
            return;
        }
    } else {
        if (func(hi) > target or func(lo) < target) {
            printf("error");
            return;
        }
    }

    while (lo + 1 < hi) {
        x = (hi + lo) / 2;
        y = func(x);
        if (y == target) {
            // 恰巧找到了这个数
            printf("%d\n", x);
            return;
        } else if (y < target) {
            // y 小于目标值
            if (is_increment) {
                lo = x;
            } else {
                hi = x;
            }
        } else {
            // y 大于目标值
            if (is_increment) {
                hi = x;
            } else {
                lo = x;
            }
        }
    }
    printf("(%d, %d)\n", lo, hi);
}