/*
 * Hokan.c: Linear Interpolation 線形補間
 */
#include <stdio.h>
#include <math.h>
#define ND 100

int Sagasu(double xx[], double x, int n)
/*
  該当区間を探す
 */
{
    int i, l, r, m, kaisuu;

    l = 0;
    r = n;
    kaisuu = (int)(log(n)/log(2)+1);
    for (i=1; i<=kaisuu; i++){
        m = (l+r)/2;
        if (xx[m] <= x) l = m;
        else r = m;
        if (xx[l+1] > x) break;
    }
    return l;
}

double Hokan(double xx[], double yy[], double x, int k)
/*
  線形補間
 */
{
    int k1;

    k1 = k+1;
    return yy[k]+(x-xx[k])*(yy[k1]-yy[k])/(xx[k1]-xx[k]);
}

int Datain(double xx[], double yy[])
/*
  テストデータ作成
  y = sin(x) (x=0,10,...,360)
 */
{
    int i, n, deg;
    double rad;

    n = 36;
    for (i=0; i<=n; i++) {
        deg = 10*i;
        rad = 3.14159265*deg/180.0;
        xx[i] = deg;
        yy[i] = sin(rad);
    }
    return n;
}

/*    ------------------    Main    ------------------    */
int main()
{
    int i, k, n;
    double x, y, xx[ND+1], yy[ND+1];
    char s[135];

    n = Datain(xx, yy);
    for (i=1; i<=4; i++) {
        printf(" x= "); gets(s); sscanf(s,"%lf",&x);
        k = Sagasu(xx, x, n);
        y = Hokan(xx, yy, x, k);
        printf(" y= %e\n", y);
    }
    return 0;
}
/* -- 実行例:戸川隼人「数値計算」岩波書店 p.148 プログラム7.1 -- */
/*
Z:\src\C>Hokan
 x= 45
 y= 7.044160e-01
 x= 135
 y= 7.044160e-01
 x= 225
 y= -7.044160e-01
 x= 315
 y= -7.044160e-01
*/