2分探索
配列から値を探す。配列の要素は昇順に並んでいるとする。
code:search.c
int search(int x, int a[], int left, int right)
{
int mid;
while (left < right) {
mid = (left + right) / 2;
if (amid < x)
left = mid + 1;
else
right = mid;
}
if (aleft == x)
return left;
return -1; /* 見つからなかった場合 */
}
mainを補って，整列した配列を渡して，試してみよう。
関数の0点を求めるのにも2分法が使える。
code:bisect.c
#include <stdio.h>
#include <math.h>
double f(double x)
{
return x * x - 2;
}
int main(void)
{
double a, b, c, fa, fb, fc;
a = 1;
b = 2;
fa = f(a); /* f(a) < 0 */
fb = f(b); /* f(b) > 0 */
while (fabs(b - a) > 0.0000001) {
c = (a + b) / 2;
fc = f(c);
if (fc > 0) {
b = c;
fb = fc;
} else {
a = c;
fa = fc;
}
}
printf("%g\n", c);
}